Cod sursa(job #1450731)

Utilizator Rares95Rares Arnautu Rares95 Data 14 iunie 2015 15:04:40
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
# include <iostream>
# include <fstream>
using namespace std;

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

struct V
{
	long long a, b;
	V operator+ (const V &other)
	{
		V res;
		res.a = this->a + other.a;
		res.b = this->b + other.b;
		return res;
	}
	V operator- (const V &other)
	{
		V res;
		res.a = this->a - other.a;
		res.b = this->b - other.b;
		return res;
	}
	V operator* (const long long other)
	{
		V res;
		res.a = this->a * other;
		res.b = this->b * other;
		return res;
	}
};

long long GCD(long long a, long long b, long long c, V &sol)
{
	V V0, V1, Vr;
	V0 = { 1, 0 };
	V1 = { 0, 1 };
	long long q, r;
	while (b)
	{
		q = a / b;
		Vr = (V0 - (V1 * q));
		r = a % b;
		a = b;
		b = r;
		V0 = V1;
		V1 = Vr;
	}
	sol = V0;
	return a;
}

int main()
{
	int testsNumber;
	long long a, b, c;
	V v;

	fin >> testsNumber;

	for (int i = 0; i < testsNumber; ++i)
	{

		fin >> a >> b >> c;
		long long gcd = GCD(a, b, c, v);

		if (c % gcd)
			fout << "0 0\n";
		else
			fout << v.a * c / gcd << ' ' << v.b * c / gcd << '\n';

	}

	fin.close();
	fout.close();

	return 0;
}