Cod sursa(job #1040044)

Utilizator DaniEsDani Stetcu DaniEs Data 23 noiembrie 2013 21:39:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int T;
int GCD(int A, int B, int &X, int &Y)
{
    if(B==0)
    {
        X=1;Y=0;
        return A;
    }
    int D,X0,Y0;
    D=GCD(B,A%B,X0,Y0);
    X=Y0;
    Y=X0-(A/B)*Y0;
    return D;
}
int main()
{
    fin>>T;
    while(T--)
    {
        int A,B,C,D,X,Y;
        fin>>A>>B>>C;
        D=GCD(A,B,X,Y);
        if(C%D==0)
            {
                fout<<1LL*X*(C/D)<<" "<<1LL*Y*(C/D)<<"\n";
            }
        else
            {
                fout<<"0 0\n";
            }

    }
    return 0;
}