Cod sursa(job #2886343)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 7 aprilie 2022 17:01:11
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <vector> 
#include <algorithm> 
#include <string> 
#include <cassert> 
#include <algorithm> 
#include <set> 
#include <iomanip> 
#include <queue> 
#include <deque> 
#include <unordered_set> 
#include <unordered_map> 
#include <functional> 
#include <cmath> 
#include <map> 
#include <random> 
#include <chrono> 
#include <cstdio> 
#include <bitset> 
#include <numeric> 

using namespace std;

typedef long long ll;

ll d;

pair<ll, ll> gcd(ll a, ll b) {
	if (b == 0) {
		d = a;
		return { 1, 0 };
	}
	ll c = a / b;
	pair<ll, ll> it = gcd(b, a - b * c);

	return { it.second, it.first - it.second * c };
}

vector<pair<ll, ll>> solve(ll a, ll b, ll c) {
	auto it = gcd(a, b);
	assert(a * it.first + b * it.second == d);
	if (c % d) return {};
	c = c / d;
	it.first *= c;
	it.second *= c;
	return { it };
}


signed main() {
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdin);
	int t;
	cin >> t;
	while (t--) {
		ll a, b, c;
		cin >> a >> b >> c;
		auto sol = solve(a, b, c);
		if (sol.empty()) {
			cout << "0 0\n";
			continue;
		}
		assert((int)sol.size() == 1);
		assert(a * sol[0].first + b * sol[0].second == c);
		cout << sol[0].first << " " << sol[0].second << "\n";
	}
}