Cod sursa(job #2499416)

Utilizator radustn92Radu Stancu radustn92 Data 26 noiembrie 2019 02:39:01
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int tests;
int a, b, c;

int extendedEuler(int a, int b, long long& resultX, long long& resultY) {
	if (b == 0) {
		// 1 * gcd(a, b) + 0 * 0 = gcd(a, b)
		resultX = 1; resultY = 0;
		return a;
	}

	int d = extendedEuler(b, a % b, resultX, resultY);

	long long newResultX = resultY;
	long long newResultY = resultX - resultY * (a / b);

	resultX = newResultX;
	resultY = newResultY;

	return d;
}

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

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> tests;
	for (int test_no = 1; test_no <= tests; test_no++) {
		cin >> a >> b >> c;

		long long resultA, resultB;
		int cmmdc = extendedEuler(a, b, resultA, resultB);

		if (c % cmmdc) {
			cout << "0 0\n";
		} else {
			cout << resultA * (c / cmmdc) << " " << resultB * (c / cmmdc) << "\n";
		}
	}
	return 0;
}