Cod sursa(job #388820)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 31 ianuarie 2010 00:45:43
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <cstdio>

#define file_in "euclid3.in"
#define file_out "euclid3.out"

int T,a,b,c;

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


int main()
{
	int x,y,d;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &T);
	
	while(T--)
	{
		scanf("%d %d %d", &a, &b, &c);
		
		d=euclid(a,b,x,y);
		
		if (c%d!=0)
		{
			printf("0 0\n");
		}
		else
		{
			printf("%d %d\n", x*(c/d),y*(c/d));
		}
	}
	
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}