Cod sursa(job #702120)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 1 martie 2012 19:44:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
int t,a,b,c,d;
void euclid(int a, int b, int &d, int &x, int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		d=a;
	}
	else
	{
		int x0,y0;
		euclid(b,a%b,d,x0,y0);
		x=y0;
		y=x0-(a/b)*y0;
	}
}
int div(int x, int y)
{
	if(y==0)
		return x;
	else
		return div(y,x%y);
}
int main()
{
	int x,y,i;
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%d", &t);
	for(i=1;i<=t;i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		d=div(a,b);
		if(c%d)
			printf("0 0\n");
		else
		{
			euclid(a,b,d,x,y);
			x*=c/d;
			y*=c/d;
			printf("%d %d\n", x, y);
		}
	}
	return 0;
}