Pagini recente » Cod sursa (job #2476035) | Cod sursa (job #2778613) | Cod sursa (job #2699648) | Cod sursa (job #668271) | Cod sursa (job #2360941)
#include <cstdio>
struct EuclidExtins {
int x;
int y;
};
int gcd(int a, int b) {
while (b > 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
EuclidExtins euclid_extins(int a, int b, int d) {
if (b == 0)
return {d / a, 0};
else {
EuclidExtins lastSol = euclid_extins(b, a % b, d);
int c = a / b;
return {lastSol.y, lastSol.x - c * lastSol.y};
}
}
int main() {
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
int t;
scanf("%d", &t);
for (int test = 0; test < t; test++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
int d = gcd(a, b);
if (c % d != 0)
printf("0 0\n");
else {
EuclidExtins sol = euclid_extins(a, b, d);
int k = c / d;
printf("%d %d\n", sol.x * k, sol.y * k);
}
}
return 0;
}