Cod sursa(job #1892620)

Utilizator k.bruenDan Cojocaru k.bruen Data 25 februarie 2017 10:16:34
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
using std::pair;

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

int t, a, b, c;

pair<long long, long long> euclid_extended(int x, int y)
{
	if (y == 0)
		return { 1,0 };
	auto p = euclid_extended(y, x%y);
	return { p.second, p.first - (x / y)*p.second };
}


int main(void) {
	in >> t;
	for (; t > 0; t--) {
		in >> a >> b >> c;
		auto result = euclid_extended(a, b);
		auto d = result.first * a + result.second * b;

		if (c % d != 0) {
			out << "0 0\n";
		}
		else {
			out << result.second * (c / d) << " " << result.first * (c / d) << '\n';
		}
	}
}