Cod sursa(job #3226617)

Utilizator dorufDoru Floare doruf Data 22 aprilie 2024 11:40:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
#define eb emplace_back

int32_t main() {
	//#ifdef ONLINE_JUDGE
    freopen("euclid3.in", "r", stdin);
		freopen("euclid3.out", "w", stdout);
	//#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

 	int T; for (cin >> T; T; --T) {
 		int a, b, c, x, y; cin >> a >> b >> c;
 		function<int(int,int,int&,int&)> euclid = [&](int a, int b, int& x, int& y) {
 			if (!b)	{x = 1; y = 0; return a;}
			ll x0, y0, d;
			d = euclid(b, a%b, x0, y0);
			x = y0;
			y = x0 - (a / b) * y0;
			return d; 			
 		};
 		int d = euclid(a, b, x, y);
 		if (c % d) x = y = 0;
 		c /= d;
 		cout << x * c << ' ' << y * c << '\n';
 	}
}