Cod sursa(job #1542421)
| Utilizator | Data | 5 decembrie 2015 12:56:37 | |
|---|---|---|---|
| Problema | Algoritmul lui Euclid extins | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.65 kb |
#include <fstream>
using namespace std;
int gcd(int A, int B, int &X, int &Y) {
if (B == 0) {
X = 1;
Y = 0;
return A;
}
int x0, y0, D;
D = gcd(B, A % B, x0, y0);
X = y0;
Y = x0 - (A / B) * y0;
return D;
}
int main() {
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int T;
for (fin >> T; T; --T) {
int A, B, C;
fin >> A >> B >> C;
int D, X, Y;
D = gcd(A, B, X, Y);
if (C % D)
fout << "0 0" << "\n";
else
fout << X * (C / D) << ' ' << Y * (C / D) << "\n";
}
return 0;
}
