Cod sursa(job #477922)

Utilizator azotlichidAdrian Vladu azotlichid Data 16 august 2010 17:20:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>

int gcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1, y = 0;
		return a;
	} else {
		int xx, yy, d;
		d = gcd(b, a%b, xx, yy);
		x = yy, y = xx - (a/b) * yy;
		return d;
	}
}

int main() {
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	int T, a, b, c, d, xx, yy;
	for (scanf("%d", &T); T; T--) {
		scanf("%d %d %d", &a, &b, &c);
		d = gcd(a, b, xx, yy);
		if (c % d == 0) {
			printf("%d %d\n", xx * (c/d), yy * (c/d));
		} else
			printf("0 0\n");
	}
	return 0;
}