Cod sursa(job #649621)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 16 decembrie 2011 13:57:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<cstdio>
void read(),solve();
int t,a,b,c,d,cmmdc(int a,int b,int &x,int &y);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%d",&t);
}
void solve()
{
	for(;t;--t)
	{
		scanf("%d%d%d",&a,&b,&c);
		int x,y;
		d=cmmdc(a,b,x,y);
		if(c%d){printf("0 0\n");continue;}
		printf("%d %d\n",x*(c/d),y*(c/d));
	}
}
int cmmdc(int A,int B,int &X,int &Y)
{
	if(!B)
	{
		X=1;
		Y=0;
		return A;
	}
	int x0,y0,d;
	d=cmmdc(B,A%B,x0,y0);
	X=y0;
	Y=x0-(A/B)*y0;
	return d;
}