Cod sursa(job #659376)

Utilizator XbyteAvram Florin Xbyte Data 10 ianuarie 2012 16:28:01
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<cstdio>

using namespace std;

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

int T,a,b,c;

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

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