Pagini recente » Autentificare | Cod sursa (job #3358662) | Cod sursa (job #3358325) | Cod sursa (job #3358479) | Cod sursa (job #3358169)
#include <stdio.h>
// ALGORITMUL LUI EUCLID EXTINS - ecuatia a*x + b*y = c
// din curs stim ca pentru orice a, b exista x, y astfel incat a*x + b*y = gcd(a, b) <- asta e Lema lui Bezout
long long euclid_extins(long long a, long long b, long long *x, long long *y) {
if (b == 0) {
// cazul de baza: gcd(a, 0) = a si a*1 + 0*0 = a, deci x=1, y=0
*x = 1;
*y = 0;
return a;
}
long long x1, y1; // solutia pentru subproblema mai mica
long long d = euclid_extins(b, a % b, &x1, &y1);
// relatia de reconstructie din curs: x = y1 si y = x1 - (a/b) * y1
*x = y1;
*y = x1 - (a / b) * y1;
return d; // gcd-ul ramane acelasi pe tot parcursul recursiei
}
int main() {
FILE *fin = fopen("euclid3.in", "r");
FILE *fout = fopen("euclid3.out", "w");
if (fin == NULL) {
printf("nu gasesc fisierul euclid3.in\n");
return 1;
}
int T; // numarul de teste
fscanf(fin, "%d", &T);
int i;
for (i = 0; i < T; i++) {
long long a, b, c;
fscanf(fin, "%lld %lld %lld", &a, &b, &c);
long long x, y;
long long d = euclid_extins(a, b, &x, &y);
// acum avem: a*x + b*y = d (unde d = gcd(a,b))
if (c % d != 0) {
// din curs: daca c nu se divide cu d, nu exista solutie
fprintf(fout, "0 0\n");
} else {
// inmultim toata ecuatia cu c/d ca sa trecem de la a*x + b*y = d la a*(x*c/d) + b*(y*c/d) = c
long long cat = c / d;
x = x * cat;
y = y * cat;
fprintf(fout, "%lld %lld\n", x, y);
}
}
fclose(fin);
fclose(fout);
return 0;
}