Cod sursa(job #2194587)

Utilizator IamNeganradu radu IamNegan Data 13 aprilie 2018 19:50:43
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <unordered_set>

std::ifstream fin("euclid3.in");
std::ofstream fout("euclid3.out");

#define maxim(a, b) ((a > b) ? a : b)
#define FOR(i, a, b) for (i = a; i <= b; ++i)


int gcdExtended(int a, int b, int *x, int *y)
{
	if (a == 0)
	{
		*x = 0;
		*y = 1;
		return b;
	}

	int x1, y1;
	int gcd = gcdExtended(b%a, a, &x1, &y1);


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

	return gcd;
}

int main()
{
	int T;
	fin >> T;

	while (T-- > 0) {
		int A, B, C;
		fin >> A >> B >> C;
		int D, X, Y;
		D = gcdExtended(A, B, &X, &Y);

		if (C%D) {
			fout << 0 << '\n';
		}
		else
			fout << X * (C / D)<< ' ' << Y * (C / D) << '\n';
	}

	system("pause");
	return 0;
}