Cod sursa(job #416474)

Utilizator andreirulzzzUPB-Hulea-Ionescu-Roman andreirulzzz Data 12 martie 2010 20:20:50
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <cstdio>

long euclid(long a, long b, long &x, long &y)
	{
	if (b==0)
		{
		x=1;
		y=0;
		return a;
		}
	long x1,y1,d;
	d=euclid(b,a%b,x1,y1);
	x=y1;
	y=x1-(a/b)*y1;
	return d;
	}

int main()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	long t,a,b,c,i;
	scanf("%ld",&t);
	for (i=1;i<=t;i++)
	{
		scanf("%ld %ld %ld",&a,&b,&c);
		long d,xx,yy;
		d=euclid(a,b,xx,yy);
		if (c%d)
			printf("0 0\n");
		else
			printf("%ld %ld\n",xx*(c/d),yy*(c/d));
	}
	return 0;
}