Cod sursa(job #1996545)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 1 iulie 2017 20:44:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <tuple>

using namespace std;

tuple<int, int, int> gcd(int a, int b) {
    if (b == 0) {
        return make_tuple(a, 1, 0);
    } else {
        const auto& x = gcd(b, a % b);
        return make_tuple(get<0>(x),
                          get<2>(x),
                          get<1>(x) - get<2>(x) * (a / b));
    }
}

int main() {
#ifdef INFOARENA
    ifstream cin("euclid3.in");
    ofstream cout("euclid3.out");
#endif
    int num_tests; cin >> num_tests;
    while (num_tests--> 0) {
        int a, b, c; cin >> a >> b >> c;
        const auto& gcd_values = gcd(a, b);
        if (c % get<0>(gcd_values)) {
            cout << "0 0\n";
        } else {
            c /= get<0>(gcd_values);
            cout << get<1>(gcd_values) * c << ' '
                 << get<2>(gcd_values) * c << '\n';
        }
    }
}