Cod sursa(job #2323761)

Utilizator igsifvevc avb igsi Data 19 ianuarie 2019 17:25:49
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <tuple>
#include <utility>

void euclid_extins(int a, int b, int& d, int& x, int& y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		d = a;
		return;
	}

	int x0{0}, y0{0};
	euclid_extins(b, a % b, d, x0, y0);

	x = y0;
	y = x0 - a/b * y0;
}

std::pair<int, int> euclid(int a, int b, int c)
{
	int x{0}, y{0}, d{0};

	euclid_extins(a, b, d, x, y);

	if (c % d != 0)
	{
		x = y = 0;
	}
	else
	{
		x *= c / d;
		y *= c / d;
	}

	return std::make_pair(x, y);
}

int main()
{
	std::ifstream fin("euclid3.in");
	std::ofstream fout("euclid3.out");

	int T, a, b, c, x, y;

	for(fin >> T; T; --T)
	{
		fin >> a >> b >> c;

		std::tie(x, y) = euclid(a, b, c);
		fout << x << ' ' << y << '\n';
	}

	return 0;
}