Pagini recente » Cod sursa (job #2966600) | quarter_2018 | Cod sursa (job #1499687) | Cod sursa (job #1965404) | Cod sursa (job #3233198)
#include <iostream>
#include <fstream>
#include <tuple>
using namespace std;
// Function to perform the Extended Euclidean Algorithm
tuple<int, int, int> extended_gcd(int a, int b) {
if (b == 0)
return make_tuple(a, 1, 0);
int g, x, y;
tie(g, x, y) = extended_gcd(b, a % b);
return make_tuple(g, y, x - (a / b) * y);
}
// Function to find one solution of the equation a * x + b * y = c
bool find_solution(int a, int b, int c, int &x0, int &y0, int &g) {
tie(g, x0, y0) = extended_gcd(a, b);
if (c % g != 0)
return false;
x0 *= c / g;
y0 *= c / g;
return true;
}
int main() {
ifstream infile("euclid3.in");
ofstream outfile("euclid3.out");
if (!infile || !outfile) {
cerr << "Error opening file" << endl;
return 1;
}
int T;
infile >> T;
for (int i = 0; i < T; ++i) {
int a, b, c;
infile >> a >> b >> c;
int x, y, g;
if (find_solution(a, b, c, x, y, g)) {
// Solution exists, adjust x and y to be within the desired range if necessary
outfile << x << " " << y << endl;
} else {
// No solution exists
outfile << "0 0" << endl;
}
}
infile.close();
outfile.close();
return 0;
}