Cod sursa(job #572985)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 5 aprilie 2011 19:44:43
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
# include <fstream>
using namespace std;
std :: ifstream f ("euclid3.in");
std :: ofstream g ("euclid3.out");
int T, a, b, c, d, s, t;
int euclid_extins (int a, int b, int &s, int &t){
	int r, c, s1, s2, t1, t2;
	if (!b){
		s = 1;
		t = 0;
		return a;
	}
	s = 0; t = 1;
	s1 = 1; t1 = 0;
	s2 = 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 (){
	for (f >> T; T > 0; --T){
		f >> a >> b >> c;
		d = euclid_extins (a, b, s, t);
		if (c % d) g << "0 0\n";
		else g << s * (c / d) << ' ' << t * (c / d) << '\n';
	}
	g.close ();
	return 0;
}