Cod sursa(job #1394626)

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

using namespace std;

void extendedEuclid(int a, int b, int *c, int *x, int *y) {
//	cout << a << " " << b << " " << *c << endl;
       	if (b == 0) {
		*x = (*c) % a == 0 ? 1 : 0;
		*c = *c / a;
		*y = 0;
		return;
	}

	int x0{0}, y0{0};
	extendedEuclid(b, a % b, c, &x0, &y0);
//	cout << x0 << " " << y0 << endl;
	if (x0 != 0 || y0 != 0) {
		*y = x0 - a / b * y0;
		*x = y0;
	}
}

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

	for (int i = 0; i < n; ++i) {
		f >> a >> b >> c;
		int x{0}, y{0};
		extendedEuclid(a, b, &c, &x, &y);
		g << x * c << " " << y * c<< "\n";
//		cout << endl << endl;
	}

	return 0;
}