Cod sursa(job #194417)

Utilizator wefgefAndrei Grigorean wefgef Data 10 iunie 2008 15:17:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <cstdio>

void gcd(int a, int b, int& x, int& y, int &c) {
	if (!b) {
		x = 1;
		y = 0;
		c = a;
		return;
	}
	int x2, y2;
	gcd(b, a%b, x2, y2, c);
	x = y2;
	y = x2 - y2 * (a/b);
}

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