Cod sursa(job #373300)

Utilizator savimSerban Andrei Stan savim Data 13 decembrie 2009 14:24:36
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.49 kb
#include <stdio.h>

int T, a, b, c, d, X, Y, X0, Y0;

void get_sol(int a, int b) {
	if (b == 0) {
    	X = X0 = 1;
		Y = Y0 = 0;
		d = a;
	}
	else {
		get_sol(b, a % b);

		X = Y0;
		Y = X0 - (a / b) * Y0;

		X0 = X;	Y0 = Y;
	}
}

int main() {

	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);

	scanf("%d", &T);
	while (T--) {
    	scanf("%d %d %d", &a, &b, &c);
		get_sol(a, b);

		if (c % d) printf("0 0\n");
		else printf("%d %d\n", X * c / d, Y * c / d); 
	}	

	return 0;
}