Cod sursa(job #654747)

Utilizator andunhillMacarescu Sebastian andunhill Data 30 decembrie 2011 20:57:51
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

int T;
int rest[101];
int x[101], y[101];

pair<pair<int, int>, int> ite(int a, int b)
{	int i, q;
	
	x[0] = y[0] = 0;
	q = a / b;
	rest[0] = a - b * q;
	if(rest[0] == 0) return make_pair(make_pair(x[0], y[0]), a);
	x[0] = 1; y[0] = -q;
	
	q = b / rest[0];
	rest[1] = b - q * rest[0];
	x[1] = -q; y[1] = 1 + (a/b) * q;
	if(rest[1] == 0) return make_pair(make_pair(x[0], y[0]), rest[0]);
	
	for(i = 2; rest[i - 1]; i++)
	{	q = rest[i - 2] / rest[i - 1];
		rest[i] = rest[i - 2] - q * rest[i - 1];
		x[i] = x[i - 2] - q * x[i - 1];
		y[i] = y[i - 2] - q * y[i - 1];
	}
	return make_pair(make_pair(x[i - 2], y[i - 2]), rest[i - 2]);
}

int main()
{	int i, a, b, c;
	pair<pair<int, int>, int>p;
	
	f>>T;
	for(i = 1; i <= T; i++)
	{	f>>a>>b>>c;
		p = ite(a, b);
		if(c % p.second)
			g<<"0 0"<<'\n';
		else g<<p.first.first * c / p.second<<" "<<p.first.second * c / p.second<<'\n';
	}
	return 0;
}