Cod sursa(job #2038949)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 14 octombrie 2017 10:12:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL T;
LL d;

pair<LL, LL> euclid(LL a, LL b) {
	if(!b) {
		d = a;
		return {1, 0};
	}

	auto result = euclid(b, a % b);
	return { result.second, result.first - (a / b) * result.second };
}

int main() {

	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);

	scanf("%lld ", &T);

	while(T--) {
		LL a, b, c;
		scanf("%lld %lld %lld ", &a, &b, &c);

		auto result = euclid(a, b);

		if(c % d)
			printf("0 0\n");

		else printf("%lld %lld\n", result.first * (c / d), result.second * (c / d));
	}

	return 0;
}