Pagini recente » Cod sursa (job #1830105) | Cod sursa (job #2459650) | Cod sursa (job #850346) | Cod sursa (job #2269209) | Cod sursa (job #2471833)
#include <bits/stdc++.h>
using namespace std;
// Function for extended Euclidean Algorithm
int gcdExtended(int a, int b, int *x, int *y) {
// Base Case
if (a == 0) {
*x = 0;
*y = 1;
return b;
}
int x1, y1; // To store results of recursive call
int gcd = gcdExtended(b%a, a, &x1, &y1);
// Update x and y using results of recursive call
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}
int main()
{
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
int t, x, y, a, b, c;
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &a, &b, &c);
int g = gcdExtended(a, b, &x, &y);
if (c % g) printf("0 0\n");
else printf("%d %d\n", x * (c / g), y * (c / g));
}
return 0;
}