Cod sursa(job #439204)

Utilizator raduiris94Alexa Radu raduiris94 Data 11 aprilie 2010 14:02:27
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <cstdio> 
int extended_gcd(int a, int b, int *x, int *y){ 
	if(b == 0)
	{     
		*x = 1;   
		*y = 0;   
		return a; 
	} 
	int lcx, lcy, d;   
	d = extended_gcd(b, a%b, &lcx, &lcy);   
	*x = lcy; 
	*y = lcx-lcy*(a/b); 
	return d; 
}   
int main()
{   
	freopen("euclid3.in", "r", stdin);   
	freopen("euclid3.out", "w", stdout);  
	int a, b, c, n;  
	scanf("%d", &n);   
	for(int i = 0; i < n; i++)
	{   
		scanf("%d %d %d", &a, &b, &c); 
		int x, y, d; 
		d = extended_gcd(a, b, &x, &y); 
		if(c%d)    
			printf("0 0\n");     
		else    
			printf("%d %d\n", x*(c/d), y*(c/d)); 
	} 
	return 0; 
}