Cod sursa(job #967247)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 27 iunie 2013 14:03:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
#define ll long long
ll XA,XB,YA,YB;
ll n,i,Xsol,Ysol;

ll gcd(ll a,ll b) {

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

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

     if (a==b) {
        XA-=XB;
        YA-=YB;
        a=0;
        return gcd(a,b);
    }

    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);
    }
}
int main() {
   f>>n;

   for(i=1;i<=n;++i){
     ll xx,yy,cc;
     XA=1,YA=0,XB=0,YB=1;
     f>>xx>>yy>>cc;
    ll xind=1,yind=1;
    if (xx<0) xind=-1,xx=-xx;
    if (yy<0) yind=-1,yy=-yy;
     ll GC=gcd(xx,yy);
    ll fact=cc/GC;


     if (cc%GC!=0) g<<0<<" "<<0<<'\n';
     else
     g<<Xsol*fact*xind<<" "<<Ysol*fact*yind<<'\n';
   }

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