Cod sursa(job #473944)
Utilizator | aladin aladinn aladin | Data | 1 august 2010 20:14:33 |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.46 kb |
#include <cstdio>
int t,a,b,c;
int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
scanf("%d",&t);
for (;t;--t)
{
scanf("%d %d %d",&a,&b,&c);
int d=a,i=b,r=a%b,nr=0,v[10000];
while (r!=0)
++nr,v[nr]=d/i,d=i,i=r,r=d%i;
if (c%i) printf("0 0\n"); else
{
int x=0,y=1; c/=i;
for (i=nr;i>0;--i)
d=x,x=y,y=d-v[i]*y;
printf("%d %d\n",x*c,y*c);
}
}
return 0;}