Cod sursa(job #3121362)

Utilizator IanisBelu Ianis Ianis Data 12 aprilie 2023 10:07:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
#define endl '\n'
#endif

int gcd(int a, int b, int &x, int &y) {
	if (a == 0) {
		x = 0;
		y = 1;
		return b;
	}
	int x1, y1;
	int g = gcd(b % a, a, x1, y1);

	x = y1 - (b / a) * x1;
	y = x1;

	return g;
}

pair<int, int> solve(int a, int b, int c) {
	int x, y;
	int g = gcd(a, b, x, y);
	if (c % g != 0) return {};
	x *= c / g;
	y *= c / g;
	return {x, y};
}

int main() {
	int t, a, b, c;
	fin >> t;
	while (t--) {
		fin >> a >> b >> c;
		auto ans = solve(a, b, c);
		fout << ans.first << ' ' << ans.second << endl;
	}
	return 0;
}