Cod sursa(job #2973616)

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

struct EuclidResult{
    int d, x, y;
};

EuclidResult euclid_extended(int a, int b) {
    if (!b) {
        return {a, 1, 0};
    }
    auto euclidResult = euclid_extended(b, a % b);
    int x_old = euclidResult.x;
    int y_old = euclidResult.y;
    int d = euclidResult.d;

    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 euclid_result= euclid_extended(a, b);
        int x = euclid_result.x;
        int y = euclid_result.y;
        int d = euclid_result.d;
        if (c % d == 0) {
            g << x * (c / d) << " " << y * (c / d) << "\n";
        } else {
            g << "0 0\n";
        }
    }
    return 0;
}