Cod sursa(job #2604429)

Utilizator michael_blazemihai mihai michael_blaze Data 22 aprilie 2020 17:27:54
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>

using namespace std;

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

int solve(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	} 
	int x0, y0;
	int d = solve(b, a % b, x0, y0);
	x = y0;
	y = x0 + a / b * y0;
	return d;
}

int main() {
	int t, a, b, d;
	fin >> t;
	while (t --) {
		fin >> a >> b >> d;
		int x, y;
		int c = solve(a, b, x, y);
		if (d % c == 0)
			fout << x * c / d << ' ' << y * c / d << '\n';
		else
			fout << 0 << ' ' << 0 << '\n';
	}
}