Pagini recente » Cod sursa (job #2649792) | Cod sursa (job #1351938) | Cod sursa (job #2297274) | Cod sursa (job #1550319) | Cod sursa (job #3296972)
// https://infoarena.ro/problema/euclid3
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
pair < long long int, long long int > solve_equation (long long int a, long long int b, long long int c);
void euclid_algorithm(long long int a, long long int b, long long int* d, long long int* x, long long int* y); // Euclid's Algorithm
// for finding x, y in the equation ax + by = d, where d is the highest common divisor of a and b
int main(){
int t;
long long int a, b, c; // coefficients of the equation
pair < long long int, long long int > solution;
fin >> t;
while (t--) {
fin >> a >> b >> c;
solution = solve_equation(a, b, c);
fout << solution.first << " " << solution.second << "\n";
}
fin.close();
fout.clear();
return 0;
}
pair < long long int, long long int > solve_equation (long long int a, long long int b, long long int c)
{
long long int x = 0, y = 0;
long long int highCommDiv = 0;
euclid_algorithm(a, b, &highCommDiv, &x, &y);
if (c % highCommDiv == 0)
return make_pair(x * c / highCommDiv, y * c / highCommDiv);
else //if c is not divisible by the highest common divisor of a and b, the equation has no integer solutions
return make_pair(1LL * 0, 1LL * 0); // typecast for safety
}
void euclid_algorithm(long long int a, long long int b, long long int* d, long long int* x, long long int* y)
{
if (b == 0) { // trivial solution / base case, from which we construct the algorithm upwards (recursivley)
*d = a;
*x = 1;
*y = 0;
}
else {
long long int x_0, y_0;
euclid_algorithm(b, a % b, d, &x_0, &y_0); // algorithm for highest common divisor: (a, b) becomes (b, a % b) until a is divisable by b
*x = y_0; // mathematical calcluations explained in the problem's resources, basically combining the base case with ax + by = d,
// we obtain x = y_0 and y = x_0 - (a / b) * y_0
*y = x_0 - (a / b) * y_0;
}
}