Cod sursa(job #3223342)

Utilizator thinkphpAdrian Statescu thinkphp Data 13 aprilie 2024 10:34:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#define FIN "euclid3.in"
#define FOUT "euclid3.out"

/*
Identitatea lui Bezout
ax + by = d (unde d = gcd(a,b))

gcd(a,b) = gcd(b, a mod b)

bx0 + (a mod b)y0 = d

trebuie sa aflam pe x si y astfel incat

ax + by = d

fie un a = qb + r

formam urmatorul sistem de ecuatii:

//ax + by = d

|  (qb + r)x  + by = d
|  bx0 + ry0 = d

le formulam in functie de b si r

|(qx + y)b + xr = d
| b x0 + ry0 = d
q = a/b
=> x = y0 si
   y = x0 - qy0

   void euclid(int a, int b) {

        if(b == 0) return a;

        else return euclid(b, a % b)
   }

*/

void euclid_exended(int a, int b, int *d, int *x, int *y) {

   if( b == 0 ) {

      *d = a;

      *x = 1;

      *y = 0;

   } else {
      int x1, y1;
      euclid_exended(b, a % b, d, &x1, &y1);
      *x = y1;
      *y = x1 - (a/b)*y1;
   }
}

int main(int argc, char const *argv[]) {

  int x, y, d, a, b, c, T;

  freopen(FIN, "r", stdin);

  freopen(FOUT, "w", stdout);

  scanf("%d",&T);

  while(T--) {

      scanf("%d %d %d",&a,&b,&c);
      int d, x, y;

      euclid_exended(a, b, &d, &x, &y);

      if(c%d!=0) printf("%d %d\n", 0, 0);

      else

      printf("%d %d\n", (c/d*x), (c/d)*y);
  }

  return 0;
}