Pagini recente » Cod sursa (job #2547495) | Cod sursa (job #3228609) | Cod sursa (job #287337) | Cod sursa (job #1904125) | Cod sursa (job #3287275)
// https://www.infoarena.ro/problema/euclid3
#include <iostream>
#include <fstream>
#include <exception>
/**
* @brief Computes a solution to Bezout's identity ax + by = d, where d is
* gcd(a, b). If d does not divide c, then ax + by = c does not have a solution.
*
* Complexity: O(log(N))
*/
int euclid_extended(int a, int b, int& x, int& y)
{
if (b == 0)
return x = 1, y = 0, a;
int x0, y0;
int d = euclid_extended(b, a % b, x0, y0);
x = y0;
y = x0 - (a / b) * y0;
return d;
}
int main()
{
try {
std::ifstream in("euclid3.in");
std::ofstream out("euclid3.out");
if (!in.is_open())
throw std::runtime_error("input file not found");
int T;
in >> T;
while (T--) {
int a, b, c, x, y;
in >> a >> b >> c;
int d = euclid_extended(a, b, x, y);
if (c % d == 0)
out << x * (c / d) << ' ' << y * (c / d) << '\n';
else
out << "0 0\n";
}
}
catch (const std::exception& e) {
std::cerr << e.what();
return EXIT_FAILURE;
}
}