Cod sursa(job #942508)

Utilizator MIonutMistreanu Ionut MIonut Data 22 aprilie 2013 20:00:56
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int T;
int main(){
    int s1,s2,t1=1,t2=0,y1=0,y2=1,r,c,s,t,y;
    f>>T;
    for(int a,b,d, i=1; i<=T; ++i){
        f>>a>>b>>d;
        if(b==0) g<<(d/a)<<" 0"<<'\n';
         else if(a==0)  g<<" 0"<<(d/b)<<'\n';
         else {
            s1=a;
            s2=b;
            r=a%b;
            c=a/b;
            if(b==0) g<<(d/a)<<" 0"<<'\n';
            else if(a==0)  g<<" 0"<<(d/b)<<'\n';
             while(r){
                s=s1-s2*c, t=t1-t2*c, y=y1-y2*c;
                s1=s2; t1=t2; y1=y2;
                s2=s; t2=t; y2=y;
                a=b;
                b=r;
                r=a%b;
                c=a/b;
            }
            if(d%s==0) g<<t*(d/s)<<" "<<y*(d/s)<<'\n';
            else g<<"0 0"<<'\n';
        }
    }
 g.close();
 return 0;
}