Cod sursa(job #1009524)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 13 octombrie 2013 12:52:16
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <utility>

using namespace std;

pair<int, int> euclid(int a, int b, int c)
{
	if (b == 0)
	{
		if (c % a == 0)
			return make_pair(c / a, 0);
		else return make_pair(0, 0);
	}

	else if (a % b)
	{
		pair<int, int> r = euclid(b, a % b, c);

		if ( r.first == 0 && r.second == 0)
			return r;

		return std::make_pair(r.second, r.first - (r.second * (a/b)));
	}

	else
	{
		if (c%b == 0)
		{
			return make_pair(1, c/b - a/b);
		}

		else
		{
			return make_pair(0, 0);
		}
	}
}

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

	int t; IN >> t;

	int c, a, b, x, y;

	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";
	}
}