fork(5) download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. struct Matrix2 {
  5.   int m[2][2];
  6. };
  7.  
  8. void setMatrix(struct Matrix2 *M, int a, int b, int c, int d) {
  9.   M->m[0][0] = a;
  10.   M->m[0][1] = b;
  11.   M->m[1][0] = c;
  12.   M->m[1][1] = d;
  13. }
  14.  
  15. void setMatrixE(struct Matrix2 *M) { setMatrix(M, 1, 0, 0, 1); }
  16.  
  17. struct Matrix2 calcMatrixMul(struct Matrix2 A, struct Matrix2 B) {
  18.   struct Matrix2 C;
  19.   C.m[0][0] = A.m[0][0] * B.m[0][0] + A.m[0][1] * B.m[1][0];
  20.   C.m[0][1] = A.m[0][0] * B.m[0][1] + A.m[0][1] * B.m[1][1];
  21.   C.m[1][0] = A.m[1][0] * B.m[0][0] + A.m[1][1] * B.m[1][0];
  22.   C.m[1][1] = A.m[1][0] * B.m[0][1] + A.m[1][1] * B.m[1][1];
  23.   return C;
  24. }
  25.  
  26. void vomitMatrix2(struct Matrix2 M) {
  27.   printf("(%d, %d, %d, %d)\n",
  28.          M.m[0][0],
  29.          M.m[0][1],
  30.          M.m[1][0],
  31.          M.m[1][1]);
  32. }
  33.  
  34. void LinearDiophantine(int a, int b, int *d, int *x, int *y, int *alpha, int *beta) {
  35.   struct Matrix2 M, A;
  36.   int k, r;
  37.   setMatrixE(&M);
  38.   for (;;) {
  39.     k = a / b;
  40.     r = a % b;
  41.     setMatrix(&A, 0, 1, 1, -k);
  42.     M = calcMatrixMul(A, M);
  43. /*
  44.     printf("(%d, %d) = (%d, %d) : %d\n", a, b, b, r, k);
  45.     vomitMatrix2(M);
  46. */
  47.     if (r == 0)
  48.       break;
  49.     a = b;
  50.     b = r;
  51.   }
  52.   *d  = b;
  53.   *x = M.m[0][0];
  54.   *y = M.m[0][1];
  55.   *alpha = M.m[1][0];
  56.   *beta = M.m[1][1];
  57. }
  58.  
  59. int eval(int x, int y) { return abs(x * y); }
  60.  
  61. void reduction(int x, int y, int alpha, int beta, int *x_best, int *y_best) {
  62.   int init_point, best_point, now_point, direction;
  63.   *x_best = x; *y_best = y;
  64.   init_point = best_point = eval(x, y);
  65.   if (init_point > eval(x + alpha, y + beta))
  66.     direction = +1;
  67.   else
  68.     direction = -1;
  69.   while ((now_point = eval(x += (direction * alpha), y += (direction * beta))) < init_point) {
  70. /*    printf("x = %d, y = %d\n", x, y); */
  71.     if (now_point < best_point) {
  72.       best_point = now_point;
  73.       *x_best = x; *y_best = y;
  74.     }
  75.   }
  76. }
  77.  
  78. int main() {
  79.   int a, b, s;
  80.   int d, x, y, alpha, beta;
  81.   int x_best, y_best;
  82.   printf("a = "); scanf("%d", &a); putchar('\n');
  83.   printf("b = "); scanf("%d", &b); putchar('\n');
  84.   printf("s = "); scanf("%d", &s); putchar('\n');
  85.   LinearDiophantine(a, b, &d, &x, &y, &alpha, &beta);
  86.   if (d < 0) {
  87.     x *= -1; y *= -1; d *= -1;
  88.   }
  89.   printf("(%d)a + (%d)b = %d\n", x, y, d);
  90.   if (s != d) {
  91.     if (s % d == 0) {
  92.       x = x * s / d;
  93.       y = y * s / d;
  94.       reduction(x, y, alpha, beta, &x_best, &y_best);
  95.       printf("(%d)a + (%d)b = %d\n", x_best, y_best, s);
  96.     } else {
  97.       printf("no solution.\n");
  98.     }
  99.   }  
  100.   return 0;
  101. }
  102. /* end */
  103. /* ref. http://w...content-available-to-author-only...o.jp/dp/4314001658/ chapter.1-3
  104.  *      http://w...content-available-to-author-only...o.jp/dp/4000076345/ chapter.7(2)
  105.  */
  106.  
Success #stdin #stdout 0s 1792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a = 
b = 
s = 
(0)a + (1)b = 1
(0)a + (-1076158796)b = -1076158796
https://ideone.com/lialzy
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!