fork(1) download 
  1. #include <stdio.h>
  2.  
  3. struct Matrix2 {
  4.   int m[2][2];
  5. };
  6.  
  7. void setMatrix(struct Matrix2 *M, int a, int b, int c, int d) {
  8.   M->m[0][0] = a;
  9.   M->m[0][1] = b;
  10.   M->m[1][0] = c;
  11.   M->m[1][1] = d;
  12. }
  13.  
  14. void setMatrixE(struct Matrix2 *M) { setMatrix(M, 1, 0, 0, 1); }
  15.  
  16. struct Matrix2 calcMatrixMul(struct Matrix2 A, struct Matrix2 B) {
  17.   struct Matrix2 C;
  18.   C.m[0][0] = A.m[0][0] * B.m[0][0] + A.m[0][1] * B.m[1][0];
  19.   C.m[0][1] = A.m[0][0] * B.m[0][1] + A.m[0][1] * B.m[1][1];
  20.   C.m[1][0] = A.m[1][0] * B.m[0][0] + A.m[1][1] * B.m[1][0];
  21.   C.m[1][1] = A.m[1][0] * B.m[0][1] + A.m[1][1] * B.m[1][1];
  22.   return C;
  23. }
  24.  
  25. void vomitMatrix2(struct Matrix2 M) {
  26.   printf("(%d, %d, %d, %d)\n",
  27.          M.m[0][0],
  28.          M.m[0][1],
  29.          M.m[1][0],
  30.          M.m[1][1]);
  31. }
  32.  
  33. void LinearDiophantine(int a, int b, int *d, int *x, int *y) {
  34.   struct Matrix2 M, A;
  35.   int k, r;
  36.   setMatrixE(&M);
  37.   for (;;) {
  38.     k = a / b;
  39.     r = a % b;
  40.     setMatrix(&A, 0, 1, 1, -k);
  41.     M = calcMatrixMul(A, M);
  42. /*    printf("(%d, %d) = (%d, %d) : %d\n", a, b, b, r, k); */
  43. /*    vomitMatrix2(M); */
  44.     if (r == 0)
  45.       break;
  46.     a = b;
  47.     b = r;
  48.   }
  49.   *d  = b;
  50.   *x = M.m[0][0];
  51.   *y = M.m[0][1];
  52. }
  53.  
  54. int main() {
  55.   int a, b, s;
  56.   int d, x, y;
  57.   int t;
  58.   printf("a = "); scanf("%d", &a); putchar('\n');
  59.   printf("b = "); scanf("%d", &b); putchar('\n');
  60.   printf("s = "); scanf("%d", &s); putchar('\n');
  61.   if (a < b) { t = a; a = b; b = t; }
  62.   LinearDiophantine(a, b, &d, &x, &y);
  63.   printf("(%d)a + (%d)b = %d\n", x, y, d);
  64.   if (s != d) {
  65.     if (s % d == 0) {
  66.       printf("(%d)a + (%d)b = %d\n", x * (s / d), y * (s / d), s);
  67.     } else {
  68.       printf("no solution.\n");
  69.     }
  70.   }  
  71.   return 0;
  72. }
  73. /* end */
  74. /* ref. http://w...content-available-to-author-only...o.jp/dp/4314001658/ chapter.1-3
  75.  *      http://w...content-available-to-author-only...o.jp/dp/4000076345/ chapter.7(2)
  76.  */
  77.  
Success #stdin #stdout 0s 1792KB
comments (?)
stdin 
Standard input is empty
stdout 
a = 
b = 
s = 
(134331919)a + (-134331918)b = -4
(1388131414)a + (-1119467532)b = -1074655528
https://ideone.com/oT4iJT
language:
C (gcc 8.3)
created:
11 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!