Pagini recente » Cod sursa (job #1140372) | Cod sursa (job #2602461) | Cod sursa (job #644611) | Cod sursa (job #1531070) | Cod sursa (job #889112)
Cod sursa(job #889112)
#include<stdio.h>
typedef struct {
int p, q;
} pair;
int euclid_extins(int a, int b, int *p, int *q) {
pair Va, Vb, Vaux;
Va.p = 1;
Va.q = 0;
Vb.p = 0;
Vb.q = 1;
while(b!=0) {
int q = a/b, r = a%b;
a = b; b = r;
Vaux.p = Va.p; Vaux.q = Va.q;
Va.p = Vb.p; Va.q = Vb.q;
//Vb = Va-qVb
Vb.p = Vaux.p - q*Vb.p;
Vb.q = Vaux.q - q*Vb.q;
}
*p = Va.p;
*q = Va.q;
return a;
}
int main() {
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
int t, a, b, c, gcd;
int p, q;
scanf("%d", &t);
for(; t>0; t--) {
scanf("%d%d%d", &a, &b, &c);
gcd = euclid_extins(a, b, &p, &q);
//printf("\t%d %d %d\n", gcd, p, q);
if( c%gcd!=0 ) {
printf("0 0\n");
}
else {
int cc = c/gcd;
printf("%d %d\n", p*cc, q*cc);
}
}
return 0;
}