Cod sursa(job #2973613)

Utilizator obidanDan Ganea obidan Data 1 februarie 2023 14:10:56
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>

std::tuple<int, int, int> euclid_extended(int a, int b) {
    if (!b) {
        return {a, 1, 0};
    }
    auto [d, x_old, y_old] = euclid_extended(b, a % b);

    int x_new = y_old;
    int y_new = x_old - y_old * (a / b);
    return {d, x_new, y_new};
}

int main() {
    std::ifstream f("euclid3.in");
    std::ofstream g("euclid3.out");

    int n;
    f >> n;

    for (int i = 0; i < n; ++i) {
        int a, b, c;
        f >> a >> b >> c;
        auto [d, x, y] = euclid_extended(a, b);
        if (c % d == 0) {
            g << x * (c / d) << " " << y * (c / d) << "\n";
        } else {
            g << "0 0\n";
        }
    }
    return 0;
}