Pagini recente » Cod sursa (job #2959428) | Cod sursa (job #240108) | Cod sursa (job #135563) | Cod sursa (job #1721692) | Cod sursa (job #3224130)
/*
Algoritmul lui Euclid extins
a*x + b*y = cmmdc(a,b);
Identitatea lui Bezout spune ca:
a*x + b*y = d (demonstrat), unde d = cmmdc(a,b)
cmmdc(a, b) = cmmdc(b, a mod b)
b*x0 + (a mod b) * y0 = d (1)
a*x + b*y = d (2)
Fie a = b*q+r. Inlocuim in (1) si (2) si obtinem:
(q*b + r) * x + b * y = d
b * x0 + r * y0 = d
Reformulam in functie de b si r:
(q*x + y) * b + r * x = d
x0 * b + r * y0 = d
=> x = y0 si x0 = q*x + y <=> y = x0 - q*x, dar x = y0
<=> y = x0 - q*y0
{
x = y0
si
y = x0 - q * y0
}
*/
#include <bits/stdc++.h>
#define FIN "euclidext.in"
#define FOUT "euclidext.out"
using namespace std;
void extended_euclid(int a, int b, int *d, int *x, int *y) {
if (b == 0) {
*d = a;
*x = 1;
*y = 0;
} else {
int x1, y1;
extended_euclid(b, a % b, d, &x1, &y1);
*x = y1;
*y = x1 - (a/b)*y1;
}
}
int main() {
int a, b, c, T;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &a, &b, &c);
int d, x, y;
extended_euclid(a, b, &d, &x, &y);
if (c%d != 0) printf("%d %d\n", 0, 0);
else printf("%d %d\n", (c/d*x), (c/d*y));
}
return 0;
}