Cod sursa(job #3192220)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 11 ianuarie 2024 20:08:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("euclid3.in");
ofstream out("euclid3.out");

pair<long long, long long> extended_euclid(long long a, long long b) {
	if(b == 0) { return {1, 0}; }
	pair<int, int> g = extended_euclid(b, a%b);
	return {g.second, g.first - a/b * g.second};
}

long long gcd(long long a, long long b) {
	if(b == 0) { return a; }
	return gcd(b, a%b);
}

int main() {
	int t;
	in >> t;
	while(t--) {
		long long a, b, c;
		in >> a >> b >> c;
		long long g = gcd(a, b);
		if(c % g) {
			out << 0 << ' ' << 0 << '\n';
			continue;
		}
		pair<long long, long long> ans = extended_euclid(a, b);
		out << ans.first * c / g << ' ' <<  ans.second * c / g << '\n';

	}
	return 0;
}