Cod sursa(job #494813)
| Utilizator | Data | 22 octombrie 2010 23:54:31 | |
|---|---|---|---|
| Problema | Algoritmul lui Euclid extins | Scor | 100 |
| Compilator | c | Status | done |
| Runda | Arhiva educationala | Marime | 0.51 kb |
#include <stdio.h>
void gcdext(int a, int b, int *d, int *u, int *v)
{
if(b == 0) {
*d = a;
*u = 1;
*v = 0;
} else {
int u0, v0;
gcdext(b, a%b, d, &u0, &v0);
*u = v0;
*v = u0-(a/b)*v0;
}
}
int main()
{
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
int T, a, b, c, d, u, v;
for(scanf("%d", &T); T > 0; --T) {
scanf("%d %d %d", &a, &b, &c);
gcdext(a, b, &d, &u, &v);
if(c%d == 0) {
u *= c/d;
v *= c/d;
} else u = v = 0;
printf("%d %d\n", u, v);
}
return 0;
}
