Cod sursa(job #151034)

Utilizator AlxCojocaru Alexandru Alx Data 7 martie 2008 19:24:45
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <stdio.h>
using namespace std;
long gcd(long a,long b,long &x,long &y)
{
 if (!b)
 {
  x=1;
  y=0;
  return a;
 }
 long x0,y0,d;
 d=gcd(b,a%b,x0,y0);
 x=y0;
 y=x0-(a/b)*y0;
 return d;
}
int main()
{
 freopen("euclid3.in","r",stdin);
 freopen("euclid3.out","w",stdout);
 int t,i;
 long a,b,c,x,y;
 scanf("%d\n",&t);
 for (i=0;i<t;i++)
 {
  scanf("%ld %ld %ld\n",&a,&b,&c);
  long d;
  d=gcd(a,b,x,y);
  if (c%d)
   printf("0 0\n");
  else
   printf("%ld %ld\n",x*(c/d),y*(c/d));
 }
 return 0;
}