Pagini recente » Cod sursa (job #1043641) | Cod sursa (job #2625372) | Cod sursa (job #2816549) | Cod sursa (job #223484) | Cod sursa (job #2892871)
#include <bits/stdc++.h>
using namespace std;
/*
* b * x + a % b * y = d
* b * x + (a - a / b * b) * y = d
* b * x + a * y - y * (a / b) * b = d
* a * y + b * (x - y * (a / b)) = d
* newX = y
* newY = x - y * (a / b)
*/
void euclidExtins(int a, int b, int &x, int &y, int &d) {
if (b == 0) {
x = 1;
y = 0;
d = a;
return;
}
euclidExtins(b, a % b, x, y, d);
int newX = y;
int newY = x - y * (a / b);
x = newX;
y = newY;
}
int main() {
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");
int tests;
fin >> tests;
for (int test = 1; test <= tests; ++test) {
int a, b, c;
fin >> a >> b >> c;
int gcd, x, y;
euclidExtins(a, b, x, y, gcd);
if (c % gcd) {
fout << "0 0\n";
} else {
fout << x * (c / gcd) << ' ' << y * (c / gcd) << '\n';
}
}
return 0;
}