Cod sursa(job #2270289)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 27 octombrie 2018 10:24:08
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;

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

int main()
{
	ifstream f("euclid3.in");
	ofstream g("euclid3.out");
	int n, x, y, c;
	f >> n;
	for (int i = 0; i < n; i++)
	{
		f >> x >> y >> c;
		auto p = eucl_ext(x, y);
		int d = x * p.first + y * p.second;
		if (c % d) g << "0 0\n";
		else g << p.first * (c / d) << " " << p.second * (c / d) << "\n";
	}
	return 0;
}
/*
(a, b) = d            |
ak + bl = d           |  ak + bl = bk' + (a % b)l'  |										|k = l'
(b, a % b) = d        |                             | => ak + bl = bk' + al' - bl'[a/b] =>  |l = k' - l'[a/b]
bk' + (a % b)l' = d   |                             |
a = b * [a / b] + a % b => a % b = a - b * [a / b]  |

*/