Cod sursa(job #187057)
Utilizator | Data | 30 aprilie 2008 09:57:46 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.58 kb |
#include <cstdio>
#define ll long long
int T;
ll a,b,c,d,x,y;
void euclid(ll a,ll b,ll &d,ll &x,ll &y)
{
if (b==0)
{
d=a;
x=1;
y=0;
}
else
{
ll 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",&T);
while (T)
{
--T;
scanf("%lld %lld %lld",&a,&b,&c);
euclid(a,b,d,x,y);
if (c%d!=0) printf("%d %d\n",0,0);
else printf("%lld %lld\n",x*c/d,y*c/d);
}
fclose(stdout);
}