Cod sursa(job #2909399)

Utilizator simion_bogdanSimion Bogdan-Dumitru simion_bogdan Data 13 iunie 2022 12:17:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>

using namespace std;

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

/* solutie 1 - 50 puncte
int cmmdc(int x, int y) {
	if (y == 0) {
		return x;
	}
	else {
		return cmmdc(y, x % y);
	}
}

int main() {
	int a, b, c, t;
	cin >> t;
	while (t > 0) {
		t--;
		cin >> a >> b >> c;
		int d;
		d = cmmdc(a, b);
		if ((int)(c / d) * d == c) {
			if (a == 0) {
				cout << 10 << " " << c/b << '\n';
				continue;
			}
			if (b == 0) {
				cout << c/a << " " << 10 << '\n';
				continue;
			}
			int x = c/d, y = 0;
			y = (c - a*x) / b;
			while (a * x + b * y != c) {
				x++;
				y = (c - a * x) / b;
			}
			cout << x << " " << y << '\n';
		}
		else {
			cout << 0 << " " << 0 << '\n';
		}
	}
}
*/

int euclid_extins(int a, int b, int &x, int &y) {
	int gcd;
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	int next_b = a % b;
	int aux;
	gcd = euclid_extins(b, next_b, aux, y);
	
	x = y;
	y = aux - y * (a / b);
	return gcd;
}

int main() {
	int a, b, c, t, gcd;
	cin >> t;
	while (t > 0) {
		t--;
		cin >> a >> b >> c;
		int x, y;
		gcd = euclid_extins(a, b, x, y);
		if (c % gcd != 0) {
			cout << 0 << " " << 0 << '\n';
		}
		else {
			cout << x * (c / gcd) << " " << y * (c / gcd) << '\n';
		}
	}
	return 0;
}