fork download
copy 
  1. #include <stdio.h>
  2. #define FIN "euclid3.in"
  3. #define FOUT "euclid3.out"
  4.  
  5. void euclid_extended(int a, int b, int *d, int *x, int *y) {
  6.  
  7.     if(b == 0) {
  8.       *d = a;
  9.       *x = 1;
  10.       *y = 0;
  11.     }   else {
  12.         int x1, y1;
  13.         euclid_extended(b, a%b, d, &x1, &y1);
  14.         *x = y1;
  15.         *y = x1 - (a/b)*y1;
  16.     }
  17. }
  18.  
  19. int euclid(int a, int b) {
  20.  
  21.     if(b == 0) return a;
  22.  
  23.     else return euclid(b, a % b);
  24. }
  25.  
  26. int gcd(int a, int b) {
  27.   while(a != b) {
  28.    if(a > b) {
  29.      a -= b;
  30.    } else {
  31.      b -= a;
  32.    }
  33.   }
  34.    return a;
  35. }
  36.  
  37. int euclid_it(int a, int b) {
  38.  
  39.   int r;
  40.  
  41.   while(b) {
  42.     r = a % b;
  43.     a = b;
  44.     b = r;
  45.   }
  46.   return a;
  47. }
  48.  
  49. int main(int argc, char const *argv[]) {
  50.  
  51.   int a,
  52.       b,
  53.       c;
  54.   int T;
  55.   //freopen(FIN,"r",stdin);
  56.   //freopen(FOUT,"w",stdout);
  57.   scanf("%d", &T);
  58.  
  59.   while(T--){
  60.  
  61.   scanf("%d %d %d", &a, &b, &c);
  62.   /*
  63.   int ans = euclid(a, b);
  64.  
  65.   printf("%d\n", ans);
  66.  
  67.   ans = euclid_it(a, b);
  68.  
  69.   printf("%d\n", ans);
  70.  
  71.   ans = gcd(a, b);
  72.  
  73.   printf("%d\n", ans);
  74.   */
  75.  
  76.   int d, x, y;
  77.  
  78.   euclid_extended(a,b,&d,&x,&y);
  79.  
  80.   if(c%d!=0) printf("%d %d\n", 0, 0);
  81.  
  82.   else
  83.  
  84.   printf("%d %d\n",c/d*x, c/d*y);
  85.   }
  86.   return 0;
  87. }
  88.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
3
24 15 147
24 16 104
2 4 5
stdout
copy 
98 -147
13 -13
0 0
https://ideone.com/ysdfZW
Extended Euclid's algorithm
language:
C (gcc 8.3)
created:
1 year ago
visibility:
secret

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!