Cod sursa(job #967230)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 27 iunie 2013 13:25:40
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int XA,XB,YA,YB;
int n,i,Xsol,Ysol;

int gcd(int a,int b) {

    if (a==0) {
        Xsol=XB;
        Ysol=YB;
        return b;
    }

    if (b==0) {
        Xsol=XA;
        Ysol=YA;
        return a;
    }

    if (a>b) {
        XA-=a/b*XB;
        YA-=a/b*YB;
        a%=b;
        return gcd(a,b);
    }

    if (a<b) {
        XB-=b/a*XA;
        YB-=b/a*YA;
        b%=a;
        return gcd(a,b);
    }

    if (a==b) {
        XA-=XB;
        YA-=YB;
        a=0;
        return gcd(a,b);
    }
}
int main() {
   f>>n;

   for(i=1;i<=n;++i){
     int xx,yy,cc;
     XA=1,YA=0,XB=0,YB=1;
     f>>xx>>yy>>cc;
     int GC=gcd(xx,yy);
     int fact=cc/GC;
     if (cc%GC!=0) g<<0<<" "<<0<<'\n';
     else
     g<<Xsol*fact<<" "<<Ysol*fact<<'\n';
   }

    f.close();
    g.close();
    return 0;
}