Pagini recente » Cod sursa (job #2514612) | Cod sursa (job #2969907) | Cod sursa (job #249735) | Cod sursa (job #1601000) | Cod sursa (job #1739710)
#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;
}
}
}