Cod sursa(job #627041)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 28 octombrie 2011 21:20:18
Problema Algoritmul lui Euclid extins Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#define abs(a) ( (a) < 0 ? (-a) : (a) )

using namespace std;

long long cmmdc(long long a,long long b)
{
	if (b == 0) return a;
	return cmmdc(b, a % b);
}

long long c;
void diofant(long long a, long long b, long long &x, long long &y)
{
	if (a == 1 && b == 1 || a==0 && b==1) {x = 0; y = c;} 
	else	{
		long long x1, y1;
		if (b > a)	{
			diofant (a, b-a, x1, y1);
			x = x1 - y1;
			y = y1;
		}
		else	{
			diofant (b, a-b, x1, y1);
			x = y1;
			y = x1 - y1;
			}
	}
}

int main()
{
	ifstream fin ("euclid3.in");
	ofstream fout ("euclid3.out");

	long long T,i;
	fin>>T;
	
	for (i = 0; i < T; i++)
	{
		long long a, b;
		fin>>a>>b>>c;
		
		long long d = cmmdc(a, cmmdc(b, c));
		a /= d;
		b /= d;
		c /= d;
		
		long long x, y; 
		if (cmmdc(abs(a),abs(b)) != 1) fout<<"0 0\n"; 
			else 
			{
				if(abs(a) < abs(b)) diofant(abs(b), abs(a), y, x);			
					else diofant(abs(a), abs(b), x, y);
				if(a < 0) x *= -1;
				if(b < 0) y *= -1;
				fout<<x<<" "<<y<<"\n";
			}
	}
	
	return 0;
}