Cod sursa(job #2105888)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 14 ianuarie 2018 16:15:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>

using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

/*
   consideram b = 0 => a * 1 + b * 0 = a(cmmdc)
   ( initial x = 1 si y = 0 )

   cunoastem urmatoarele relatii matematice:
   b * x0 + (a % b) * y0 = d (relatia 1)
   a * x + b * y = d (relatia 2)

   pentru a determina o pereche (x, y) cu proprietatea ceruta, notam a/b cu c => a % b = a - b * c

   relatiile 1 si 2 => b * x0 + (a - b * c) * y0 = a * x + b * y <=> b * (x0 - c * y0 - y) = a * (x - y0)

   daca egalam fiecare paranteza cu 0, se observa o solutie:
   x0 - c * y0 - y = 0 => y = x0 - c * y0
   x - y0 = 0 => x = y0
*/

inline int euclid(int a, int b, int &x, int &y)
{
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	else {
		int d, x0, y0;
		d = euclid(b, a%b, x0, y0);
	    x = y0;
		y = x0 - (a / b)*y0;
		return d;
	}
}

int main()
{
	int t;
	for (f >> t; t; t--) {
		int a, b, c, d, x, y;
		f >> a >> b >> c;
		d = euclid(a, b, x, y);
		if (c % d) g << "0 0" << '\n';
		else g << x*(c / d) << ' ' << y*(c / d) << '\n';
	}
	f.close();
	g.close();
    return 0;
}