Cod sursa(job #794450)

Utilizator akaSoarePoepscu Bogdan Ionut akaSoare Data 6 octombrie 2012 12:55:48
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <cstdio>

using namespace std;

int t, a, b, c;

 void euclid(int a, int b, int &d, int &x, int &y){
   if (b == 0) {
      d = a;
      x = 1;
      y = 0;
   }
   else {
      int x0, y0;
      euclid(b, a % b, d, x0, y0);
      x = y0;
      y = x0 - (a / b) * y0;
   }
}

int main(){
   freopen("euclid3.in","r",stdin);
   freopen("euclid3.out","w",stdout);
   scanf("%d\n",&t);
   for(int i=0;i<t;i++){
      scanf("%d %d %d\n", &a, &b, &c);
      int x;
      int y;
      int d;
      euclid(a,b,d,x,y);
      if (c % d != 0)
         printf ("0 0\n");
      else{
         x *= c / d;
         y *= c / d;
         printf ("%d %d\n", x, y);
      }
   }
   return 0;
}