Cod sursa(job #1610411)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 23 februarie 2016 15:18:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>

using namespace std;

int X, Y;

int gcd(int A, int B) {
	if (!B) {
		X = 1;
		Y = 0;
		return A;
	} else {
		int Q = gcd(B, A % B);
		
		int aux = X;
		X = Y;
		Y = aux - (A / B) * Y;
		
		return Q;
	}
}

int main() {
	ifstream fin("euclid3.in");
	ofstream fout("euclid3.out");
	fin.tie(0);
	ios_base::sync_with_stdio(false);

	int numTests; fin >> numTests;

	while (numTests--) {
		int A, B, D; fin >> A >> B >> D;

		int C = gcd(A, B);

		if (D % C == 0) {
			X *= D / C;
			Y *= D / C;

			fout << X << ' ' << Y << '\n';
		} else {
			fout << "0 0\n";
		}
	}
	fin.close();
	fout.close();
	return 0;
}