Cod sursa(job #2654193)

Utilizator raikadoCri Lu raikado Data 30 septembrie 2020 00:18:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <utility>

using namespace std;

pair<int, int> gcd_ext(int a, int b, int c) {
	if (b == 0) {
		if (c % a == 0)
			return make_pair(c/a, 0);
		else
			return make_pair(0, 0);
	}
	
	auto p = gcd_ext(b, a % b, c);
	return make_pair(p.second, p.first - (a/b) * p.second);
}


int main(int argc, char const *argv[])
{
	ifstream fin("euclid3.in");
	ofstream fout("euclid3.out");

	int T;
	fin >> T;

	for (int i = 0; i < T; ++i) {
		int a,b,c;
		fin >> a >> b >> c;
		auto p = gcd_ext(a, b, c);
		fout << p.first << ' ' << p.second << '\n';
	}

	return 0;
}