Cod sursa(job #3230539)

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

using namespace std;

typedef long long ll;

void euclid(ll a, ll b, ll& d, ll& x, ll& y) {
	if (b == 0) {
		d = a;
		x = 1;
		y = 0;
		return;
	}
	ll x0, y0;
	euclid(b, a % b, d, x0, 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;
}