Cod sursa(job #575744)

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

int euclid(int a, int b, int &s, int &t) {
	int c, r, t1, t2, s1, s2;
	if(b == 0) {
		s = 1; t = 0;
		return a;
	}
	s1 = 1; s2 = 0;
	t1 = 0; t2 = 1;
	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()
{
	int 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);
		cout << a << " * " << s << " + " << b << " * " << t << " = " << d << '\n';
		if(c % d != 0)
			g << "0 0\n";
		else
			g << s * (c / d) << ' ' << t * (c / d) << '\n';
	}
	g.close();
	return 0;
}