Cod sursa(job #1450723)

Utilizator Rares95Rares Arnautu Rares95 Data 14 iunie 2015 14:36:37
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
# include <iostream>
# include <fstream>
using namespace std;

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

struct V
{
	long long a, b;
	const V operator+ (V &other)
	{
		V res = { a, b };
		res.a += other.a;
		res.b += other.b;
		return res;
	}
	V operator- (V &other)
	{
		V res = { a, b };
		res.a -= other.a;
		res.b -= other.b;
		return res;
	}
	V operator* (long long other)
	{
		V res = { a, b };
		res.a *= other;
		res.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;
}