Cod sursa(job #1698043)

Utilizator ArkinyStoica Alex Arkiny Data 3 mai 2016 15:45:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
#include<algorithm>
#include<stack>
using namespace std;

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

void euclid_ext(int x, int y, int &a, int &b, int &r)
{
	if (y)
	{
		int a0, b0;
		euclid_ext(y, x%y, a0, b0, r);
		a = b0;
		b = a0 - b0 * (x / y);
	}
	else
		a = 1, b = 0, r = x;
}

int main()
{
	
	int T,a, b, c;
	in >> T;

	while (T--)
	{
		int a1, b1, r;
		in>> a >> b >> c;
		euclid_ext(a, b, a1, b1, r);

		if (c%r == 0)
			out << a1*(c / r) << " " << b1*(c / r) << "\n";
		else
			out << "0 0\n";

	}


	return 0;
}