Cod sursa(job #187057)

Utilizator city_guy91alex isip city_guy91 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);      
}