Pagini recente » Cod sursa (job #1644057) | Cod sursa (job #1333605) | Cod sursa (job #445062) | Cod sursa (job #2456301) | Cod sursa (job #708784)
Cod sursa(job #708784)
#include <cstdio>
long K, i, a, b, c, x, y;
int euclid(long a, long b) {
if (b == 0) {
return a;
}
return euclid(b, a%b);
}
void euclidExtins(long a, long b, long &x, long &y) {
long r, u1, v1, u2, v2;
u1 = 1; v1 = 0;
u2 = 0; v2 = 1;
do {
c = a/b;
r = a%b;
x = u1 - c * u2;
y = v1 - c * v2;
if (r != 0) {
u1 = u2, u2 = x;
v1 = v2, v2 = y;
a = b;
b = r;
}
} while (r != 0);
}
int main() {
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
scanf("%ld", &K);
for (i = 0; i < K; ++i) {
scanf("%ld %ld %ld", &a, &b, &c);
if (c % euclid(a, b) == 0) {
euclidExtins(a, b, x, y);
printf("%ld %ld\n", x, y);
} else {
printf("0 0\n");
}
}
return 0;
}