Cod sursa(job #2296440)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 4 decembrie 2018 18:00:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>

#define input "euclid3.in"
#define output "euclid3.out"

using namespace std;
typedef long long ll;

ifstream in(input);
ofstream out(output);

ll Euclid_Extins(ll A, ll B, ll &x, ll &y)
{
	if (!B)
	{
		x = 1;
		y = 0;
		return A;
	}
	else
	{
		ll x0 = 0, y0 = 0;
		ll D = Euclid_Extins(B, A % B, x0, y0);
		x = y0;
		y = x0 - y0 * (A / B);
		return D;
	}
}

void Read_Data()
{
	int test;
	in >> test;
	for (int i = 1; i <= test; i++)
	{
		ll A, B, C, D, X = 0, Y = 0;
		in >> A >> B >> C;
		D = Euclid_Extins(A, B, X, Y);
		if (C % D)
			out << 0 << " " << 0 << "\n";
		else
			out << X * (C / D) << " " << Y * (C / D) << "\n";
	}
}

int main()
{
	Read_Data();
	return 0;
}