Cod sursa(job #1538496)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 29 noiembrie 2015 11:27:27
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <algorithm>

using namespace std;

int T;

int GCD(int A,int B,int &X,int &Y)
{
    if (!B)
    {
        X = 1;
        Y = 0;
        return A;
    }

    int X1,Y1,D;

    D = GCD(B,A % B,X1,Y1);
    X = Y1;
    Y = X1 - (A / B) * Y1;

   return D;
}

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

     fin >> T;

     while (T--)
     {
         int A,B,C,X,Y;
         fin >> A >> B >> C;

         int D = GCD(A,B,X,Y);

         if (C % D)
            fout << 0 << " " << 0 << endl;
       else
            fout << X * (C / D) << " " << Y * (C / D) << endl;
     }

   return 0;
}