Cod sursa(job #1095558)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 31 ianuarie 2014 14:10:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

typedef long long i64;

i64 f ( i64 a, i64 b, i64 &x, i64 &y ) {
    if ( b==0 ) {
        x= 1;
        y= 0;
        return a;
    }

    i64 x0, y0, d;
    d= f(b, a%b, x0, y0 );

    x= y0;
    y= x0-(a/b)*y0;
    return d;
}

int main(  ) {
    int t;
    fin>>t;
    for ( ; t>0; --t ) {
        i64 a, b, c;
        fin>>a>>b>>c;

        i64 d, x= 0, y= 0;
        d= f(a, b, x, y);

        if ( c%d!=0 ) {
            x= y= 0;
        } else {
            x= x*(c/d);
            y= y*(c/d);
        }

        fout<<x<<" "<<y<<"\n";
    }

    return 0;
}