Cod sursa(job #2690129)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 23 decembrie 2020 03:04:55
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int t, a, b, d;

template<class T>
void __euclid(T a, T b, T &x, T &y) {
    T y0, x0;
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    __euclid(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
}

template<class T>
pair<T, T> extended_euclid(T a, T b, T d) {
    if (d % __gcd(a, b) != 0) {
        return make_pair(0, 0);
    }
    T x, y;
    __euclid(a, b, x, y);
    return make_pair((d / __gcd(a, b)) * x, (d / __gcd(a, b)) * y);
}

int main() {
    fin >> t;
    while (t --) {
        fin >> a >> b >> d;
        pair<int, int> ans = extended_euclid(a, b, d);
        fout << ans.first << " " << ans.second << "\n";
    }
    return 0;
}