Cod sursa(job #3287275)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 17 martie 2025 14:06:40
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
// 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;
    }
}