Cod sursa(job #1009538)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 13 octombrie 2013 13:10:55
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <utility>

using namespace std;

pair<int, int> euclid(int a, int b, int c)
{

	//daca b = 0 => a * X = c
	if (b == 0)
	{
		//daca c este divizbil cu a => x = c/a si y = oricat (il vom lua 0)
		if (c % a == 0)
			return make_pair(c / a, 0);

		//daca c nu este divizibiil cu a => x = c/a nu apartine lui Z => nu exista o solutie convenabil
		else return make_pair(0, 0);
	}

	//daca a nu este dibizibil cu b
	else if (a % b)
	{
		//se va apela functia euclid() recursiv, b devenint a iar a%b devine b (de la algoritmul lui euclid)
		pair<int, int> r = euclid(b, a % b, c);


		//daca s-a ajuns la un caz unde s-a descoperit ca nu exista solutie , transmite mai departe acest lucru
		if ( r.first == 0 && r.second == 0)
			return r;

		//matematic putem deduce ca 
		//x = y0 
		//y = x0 - c * y0
		//unde x, y sunt numerele din enunt iar x0, y0 sunt numerele de la nivelul de mai jos al stivei
		//astfel solutie este construita recursiv in functie de x0, y0 care, la cel mai de jos nivel sunt c / a, 0
		return std::make_pair(r.second, r.first - (r.second * (a/b)));
	}


	//daca b != 0 si a % b == 0 (b == cmmdc (a,b))
	else
	{

		//daca c este divizibil cu b => a * x + b * y = c =>  |
		//							 vom lua x ca fiind 1 =>  | => b * y = c - a => y = (c-a) / b) = > y = c/b - a/b; 
		if (c%b == 0) //deoarece b | a si b | b => b | (a * x + b * y)
		{
			return make_pair(1, c/b - a/b);
		}

		//altfel nu exista solutie
		else
		{
			return make_pair(0, 0);
		}
	}
}

int main()
{
	ifstream IN ("euclid3.in");
	ofstream OUT ("euclid3.out");

	int t; IN >> t;

	int c, a, b;

	for (int i = 0 ; i < t ; i++)
	{
		IN >> a >> b >> c;
		pair<int, int> r = euclid (a, b, c);
		OUT << r.first << " " << r.second << "\n";
	}
}