Cod sursa(job #2206585)

Utilizator heisenbugAnnoying Heisenbug heisenbug Data 23 mai 2018 01:01:23
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <tuple>

template <typename T>
std::tuple<T, T, T> euclid(T a, T b)
{
    T r0 = a, s0 = 1, t0 = 0;
    T r1 = b, s1 = 0, t1 = 1;

    while (r1 != 0) {
        T q = r0 / r1, r = r0 % r1, s = s0 - s1 * q, t = t0 - t1 * q;

        r0 = r1, r1 = r;
        s0 = s1, s1 = s;
        t0 = t1, t1 = t;
    }

    return std::make_tuple(r0, s0, t0);
}

int main()
{
    std::ifstream fin("euclid3.in");
    std::ofstream fout("euclid3.out");

    int t;
    fin >> t;

    while (t-- > 0) {
        long a, b, c, d, x, y;
        fin >> a >> b >> c;
        std::tie(d, x, y) = euclid(a, b);

        if (c % d == 0) {
            c /= d, x *= c, y *= c;
            fout << x << ' ' << y << '\n';
        } else {
            fout << "0 0\n";
        }
    }

    return 0;
}