Cod sursa(job #869589)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 1 februarie 2013 20:10:49
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <cstdio>
int tests;

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

int main()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	//freopen("input","r",stdin);
	scanf("%d",&tests);
	int a,b,c,x,y,d;
	while (tests--)
	{
		scanf("%d%d%d",&a, &b, &c);
		d = euclid(a, b, x, y);
		if (c % d)
			printf("0 0\n");
		else
			printf("%d %d\n",x * c / d, y * c / d);
	}
	return 0;
}