Cod sursa(job #981655)

Utilizator piroslPiros Lucian pirosl Data 7 august 2013 18:01:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
using namespace std;

int main(void)
{
	ifstream in;
	ofstream out;

	in.open("euclid3.in");
	out.open("euclid3.out");

	int n;
	in >> n;

	for(;n;--n)
	{
		int a,b,c;
		in >> a >> b >> c;
		int s,t;
		int sr[2] = {1,0};
		int tr[2] = {0,1};

		while(b!=0)
		{
			int temp = b;
			int q = a / b;
			b = a % b;
			a = temp;
			s = sr[0] - q*sr[1];
			t = tr[0] - q*tr[1];
			sr[0] = sr[1];
			sr[1] = s;
			tr[0] = tr[1];
			tr[1] = t;
		}

		if(c % a != 0) 
		{
			out << "0 0\n";
		}
		else
		{
			int d = c / a;
//			out << sr[0] << " " << tr[0] << " " << a <<'\n';
			tr[0] *= d;
			sr[0] *= d;
			out << sr[0] << " " << tr[0] << '\n';
		}
	}

	in.close();
	out.close();
	return 0;
}