Cod sursa(job #584056)

Utilizator XbyteAvram Florin Xbyte Data 23 aprilie 2011 19:47:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<cstdio>

using namespace std;

const int MaxT = 101;
const char InFile[] = "euclid3.in";
const char OutFile[] = "euclid3.out";

int T;

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

int main()
{
	freopen( InFile , "r" , stdin );
	freopen( OutFile , "w" , stdout );
	scanf("%d" , &T );
	int a,b,c,d,x,y;
	while( T-- )
		{
			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;
}