Cod sursa(job #2928268)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 22 octombrie 2022 16:47:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>

std::pair<int, int> euclid(int a, int b) {
    int x = 1, y = 0;
    if (b == 0) {
        return std::make_pair(x, y);
    }

    std::pair<int, int> pair = euclid(b, a % b);

    return std::make_pair(pair.second, pair.first - (a / b) * pair.second);
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}


int main() {
    std::ifstream input("euclid3.in");
    std::ofstream output("euclid3.out");

    int t;
    input >> t;
    while (t--) {
        int a, b, c;
        input >> a >> b >> c;
        int d = gcd(a, b);
        std::cout << c/d << '\n';
        if (c % d != 0) output << 0 << " " << 0 << '\n';
        else {
            std::pair<int, int> ans = euclid(a, b);
            output << ans.first * (c / d) << " " << ans.second * (c / d) << '\n';
        }
    }
    return 0;
}