Cod sursa(job #3230538)

Utilizator ClassicalClassical Classical Data 21 mai 2024 20:50:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void euclid(ll a, ll b, ll& d, ll& x, ll& y) {
	// a * x + b * y = d
	if (b == 0) {
		d = a;
		x = 1;
		y = 0;
		return;
	}
	ll x0, y0;
	euclid(b, a % b, d, x0, y0);
	/*
	b * x0 + (a - (a / b) * b) * y0 = d
	a * x + b * y = d
	=> 
	c = a / b
	b * (x0 - y - c * y0) = a * (x - y0)
	y = x0 - c * y0
	x = y0
	*/
	x = y0;
	y = x0 - a / b * y0;
}

int main() {
#ifdef INFOARENA
	freopen ("euclid3.in", "r", stdin);
	freopen ("euclid3.out", "w", stdout);
#endif

	int t;
	cin >> t;
	while (t--) {
		ll a, b, c, d, x, y;
		cin >> a >> b >> c;
		euclid(a, b, d, x, y);
		if (c % d) {
			cout << "0 0\n";
			continue;
		}
		x *= (c / d);
		y *= (c / d);
		assert(a * x + b * y == c);
		cout << x << " " << y << "\n";
	}

	return 0;
}