Cod sursa(job #2431221)

Utilizator ShayTeodor Matei Shay Data 18 iunie 2019 17:53:17
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <assert.h>

#define lim_ab 1000000000
#define lim_c 2000000000

int euclid_extins(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;

		return a;
	}
		
	int x0, y0, div;
	div = euclid_extins(b, a % b, x0, y0);
	x = y0;
	y = x0 - (a / b) * y0;
	
	return div;
}

int main() {
	std::ifstream in("euclid3.in");
	std::ofstream out("euclid3.out");

	int T, a, b, c, div, x, y;

	in >> T;
	assert(1 <= T && T <= 100);
	
	for (int i = 0 ; i < T ; ++i) {
		in >> a >> b >> c;
		assert(-lim_ab <= a && a <= lim_ab);
		assert(-lim_ab <= b && b <= lim_ab);
		assert(-lim_c <= c && c <= lim_c && c != 0);

		div = euclid_extins(a, b, x, y);

		if (c % div) {
			out << "0 0\n";
		} else {
			out << x * (c / div) << " " << y * (c / div) << '\n';
		}
	}
	
	return 0;
}