Cod sursa(job #2038934)

Utilizator k.bruenDan Cojocaru k.bruen Data 14 octombrie 2017 10:06:27
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
std::ifstream in("euclid3.in");
std::ofstream out("euclid3.out");

std::pair<long long, long long> ext(int a, int b) {
	if (!b) return {1, 0};
	auto p = ext(b, a % b);
	return { p.second, p.first - (a/b) * p.second };
}

int main() {
	std::ios::sync_with_stdio(false);

	int nr = 0;
	in >> nr;

	for (; nr > 0; nr--) {
		long long a, b, c;
		in >> a >> b >> c;

		auto rez = ext(a, b);
		long long x = rez.first, y = rez.second;

		long long d = a * x + b * y;
		if (c % d == 0) {
			out << x * (c / d) << ' ' << y * (c / d) << '\n';
		}
		else out << "0 0\n";
	}


	return 0;
}