Cod sursa(job #155231)

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


long cmmdc_extins(long a, long b, long &x, long &y) {  
	long x0 = 0, y0 = 1;  
	while (b) {  
		long r = a % b, q = a / b;  
		a = b;  
		b = r;        
		long aux = x0;  
		x0 = x - q * x0;  
		x = aux;  
		aux = y0;  
		y0 = y - q * y0;  
		y = aux;  
	}  
	return a;  
}  

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;  
}