Cod sursa(job #2194589)

Utilizator IamNeganradu radu IamNegan Data 13 aprilie 2018 19:56:49
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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;
	if (T >= 1 && T <= 100) {
		while (T-- > 0) {
			int A, B, C;
			fin >> A >> B >> C;
			if (A >= -1000000000 && A <= 1000000000 && B >= -1000000000 && B <= 1000000000 && C >= -2000000000 && C <= 2000000000 && C != 0) {
				int D, X, Y;
				D = gcdExtended(A, B, &X, &Y);

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

	system("pause");
	return 0;
}