Pagini recente » Cod sursa (job #1178719) | Cod sursa (job #1011369) | Cod sursa (job #36083) | Cod sursa (job #2610676) | Cod sursa (job #2466517)
#include <cstdio>
using namespace std;
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 t = 0; t < T; t++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
// a * x + b * y = d
int d = gcd(a, b);
if (c % d == 0) {
EuclidExtins sol = euclid_extins(a, b, d);
int k = c / d;
printf("%d %d\n", sol.x * k, sol.y * k);
} else {
printf("0 0\n");
}
}
return 0;
}