Cod sursa(job #1394634)

Utilizator paul-gPaul Grigoras paul-g Data 20 martie 2015 15:24:51
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <iostream>

using namespace std;

int extendedEuclid(int a, int b, int &x, int &y) {
	if (b == 0) {
		y = 0;
		x = 1;
		return a;
	}
	int x0{0}, y0{0};
	int gcd = extendedEuclid(b, a % b, x0, y0);
	y = x0 - a / b * y0;
	x = y0;
	return gcd;
}

int main(int argc, char *argv[])
{
	ifstream f{"euclid3.in"};
	ofstream g{"euclid3.out"};
	
	int n, a, b, c;
	f >> n;

	for (int i = 0; i < n; ++i) {
		f >> a >> b >> c;
		int x{0}, y{0};
		int gcd = extendedEuclid(a, b, x, y);
		if (c % gcd)
			g << "0 0\n";
		else
			g << x * (c / gcd) << " " << y * (c / gcd) << "\n";
	}

	return 0;
}