Cod sursa(job #695157)

Utilizator Marius96Marius Gavrilescu Marius96 Data 28 februarie 2012 10:50:36
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<cstdio>
struct str
{
	int x,y;
	str()
		{
			x=y=0;
		}
	str (int xx,int yy)
		{
			x=xx;
			y=yy;
		}
};
str egcd (int a,int b)
{
	if(b==0)
		return str (1,0);
	int q=a/b;
	int r=a%b;
	str st=egcd (b,r);
	int s=st.x;
	int t=st.y;
	return str (t,s-q*t);
}
int main()
{
	freopen ("euclid3.in","r",stdin);
	freopen ("euclid3.out","w",stdout);
	int t;
	scanf ("%d",&t);
	while(t--){
		int a,b,c;
		scanf ("%d%d%d",&a,&b,&c);
		str st=egcd (a,b);
		int gcd=st.x*a+st.y*b;
		if(c%gcd){
			puts ("0 0");
			continue;
		}
		printf ("%d %d\n",st.x*c/gcd,st.y*c/gcd);
	}
	return 0;
}