Cod sursa(job #1535889)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 25 noiembrie 2015 12:48:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
using namespace std;

int Q, A, B, C, D, X, Y;

inline int GCD (int A, int B, int &X, int &Y) {
   if (!B) {
      X = 1; Y = 0;
      return A;
   } else {
      int D, X1, Y1;

      D = GCD (B, A % B, X1, Y1);

      X = Y1;
      Y = X1 - (A/B) * Y1;
      return D;
   }
   return -1;
}

int main () {

   freopen ("euclid3.in" ,"r", stdin );
   freopen ("euclid3.out","w", stdout);

   scanf ("%d", &Q);
   for (int i = 1; i <= Q; i ++) {
      scanf ("%d %d %d", &A, &B, &C);

      D = GCD (A, B, X, Y);

      if (C % D)
         printf ("0 0\n");
      else
         printf ("%d %d\n", X * (C/D), Y * (C/D));
   }

   return 0;
}