Cod sursa(job #645100)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 8 decembrie 2011 15:12:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <fstream>
using namespace std;

ifstream fi ("euclid3.in");
ofstream fo ("euclid3.out");

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

int main ()
{
	int a, b, c, t, x, y, d;
	fi >> t;
	while (t--)
	{
		fi >> a >> b >> c;
		d = euclid (a, b, c, x, y);
		x *= c / d;
		y *= c / d;
		fo << x << ' ' << y << '\n';
	}	
	return 0;
}