Cod sursa(job #575778)

Utilizator deneoAdrian Craciun deneo Data 8 aprilie 2011 18:51:03
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
using namespace std;

long long euclid(long long a, long long b, long long &s, long long &t) {
	long long c, r, t1, t2, s1, s2;
	s = 1; t = 0;
	if(b == 0) {
		s = 0; t = 1;
		return a;
	}
	s1 = 0; s2 = 1;
	t1 = 1; t2 = 0;
	r = a % b; c = a / b;
	while(r) {
		s = s1 - s2 * c; s1 = s2; s2 = s;
		t = t1 - t2 * c; t1 = t2; t2 = t;
		a = b; b = r; r = a % b; c = a / b;
	}
	return b;

}

int main()
{
	long long n, i, a, b, c, s, t, d;
	ifstream f("euclid3.in");
	ofstream g("euclid3.out");
	f >> n;
	for(i = 1; i <= n; ++i)
	{
		f >> a >> b >> c;
		d = euclid(a, b, s, t);
		if(c % d != 0)
			g << "0 0\n";
		else
			g << t * (c / d) << ' ' << s * (c / d) << '\n';
	}
	g.close();
	return 0;
}