Cod sursa(job #1739710)

Utilizator tavy14tIlie Octavian tavy14t Data 9 august 2016 23:54:11
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int getGreatestCommonDivisor(int a, int b)
{
	while(b != 0)
	{
		int remainder = a % b;
		a = b;
		b = remainder;
	}
	return a;
}
/*
3
24 15 147
24 16 104
2 4 5
*/
pair<int, int> getSolution(int a, int b)
{
	static pair<int, int> finalSolution;
	if (a == 0)
		return pair<int,int>(0, 1);

	int quotient = b / a;
	int remainder = b % a;
	b = a;
	a = remainder;
	pair<int, int> tempSolution = getSolution(a, b);

	finalSolution.first = tempSolution.second - quotient * tempSolution.first;
	finalSolution.second = tempSolution.first;
	return finalSolution;
}

int main()
{
	char noTests;
	fin >> noTests;
	for (int i = 0; i < noTests; i++)
	{
		int a, b, c;
		fin >> a >> b >> c;
		int gcd = getGreatestCommonDivisor(a, b);
		if (c % gcd != 0)
			fout << "0 0\n";
		else
		{
			pair<int, int> solution = getSolution(a, b);
			solution.first *= c / gcd;
			solution.second *= c / gcd;
			fout << solution.first << " " << solution.second << endl;
		}
	}
}