Cod sursa(job #155225)

Utilizator zobicaMarin Marin zobica Data 11 martie 2008 20:12:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>


long cmmdc_extins(long a, long b, long &x, long &y) {
	if (!b) {           
		x = 1;  
		y = 0; 
		return a;
	} 
	long x0, y0;  
	long d = cmmdc_extins(b, a % b,  x0, y0);  
	x = y0;  
	y = x0 - (a / b) * y0;  
	return d;
}

int main() {
	freopen("euclid3.in", "r",stdin);
	freopen("euclid3.out", "w",stdout);
	long T;
	scanf("%ld", &T);
	for (long i = 0; i < T; i ++) {
		long a, b, d, c;    
		scanf("%ld %ld %ld", &a, &b, &c);
		long x = 1, y = 0;
		d = cmmdc_extins(a, b, x, y);
		if (c % d) {
			printf("0 0\n");
			continue;
		}
		x *= (c/d);
		y *= (c/d);
		printf("%ld %ld\n", x, y);
	}    

	fclose(stdin);
	fclose(stdout);

	return 0;
}