Cod sursa(job #1607540)
Utilizator | Data | 21 februarie 2016 12:49:18 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <stdio.h>
#define ll long long
void gcd(ll x,ll y,ll *d,ll *a,ll *b)
{
if (x==0)
{
*d=y;
*a=0;
*b=1;
} else
{
ll x1,y1;
gcd(y%x,x,d,&x1,&y1);
*a=y1-(y/x)*x1;
*b=x1;
}
}
int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
ll x,y,a,b,d,z,k;
scanf("%lld",&k);
while (k--)
{
scanf("%lld %lld %lld",&x,&y,&z);
gcd(x,y,&d,&a,&b);
if (z%d) puts("0 0"); else
printf("%lld %lld\n",a*z/d,b*z/d);
}
return 0;
}