Cod sursa(job #523264)

Utilizator unudoitreiRusu Alexandru unudoitrei Data 17 ianuarie 2011 16:48:41
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream.h>
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
long long n,a,b,c,d,i,s,t;
 
long long euclidextins(long long a, long long b, long long &s, long long &t)
{   long long r,q,s1,s2,t1,t2;
    if(!b) {s=1; t=0; return a;}
    s1=1; s2=0; t1=0; t2=1;
    r=a%b; q=a/b;
    for(;r;)
    {   s=s1-s2*q; s1=s2; s2=s;
        t=t1-t2*q; t1=t2; t2=t;
        a=b; b=r; r=a%b; q=a/b;
    }
    s=s2; t=t2;
    return b;

 
int main()
{   fin>>n;
    for(;n;--n)
    {   fin>>a>>b>>c;
        d=euclidextins(a,b,s,t);
        if(c%d) fout<<"0 0"<<'\n';
        else {c/=d; fout<<c*s<<" "<<c*t<<'\n';}
    }
    fout.close(); return 0;
}