Cod sursa(job #1538496)
Utilizator | 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;
}