Cod sursa(job #1396931)

Utilizator howsiweiHow Si Wei howsiwei Data 23 martie 2015 09:54:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <cstdio>
#include <functional>
#include <tuple>
using namespace std;

pair<int,int> solve(int a, int b, int c)
{
	function<pair<int,int>(int,int)>
	f = [&](int a, int b)->pair<int,int> {
		if (a == 0) {
			return c%b == 0 ? make_pair(0, c/b) : make_pair(0, 0);
		}
		int x, y;
		tie(x, y) = f(b%a, a);
		return x != 0 || y != 0 ? make_pair(y-b/a*x, x) : make_pair(0, 0);
	};
	return f(a, b);
}

int main()
{
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	int ntest;
	cin >> ntest;
	for (int test = 1; test <= ntest; test++) {
		int a, b, c;
		cin >> a >> b >> c;
		int x, y;
		tie(x, y) = solve(a, b, c);
		printf("%d %d\n", x, y);
	}
}