Cod sursa(job #2728376)

Utilizator Vlad.Vlad Cristian Vlad. Data 23 martie 2021 10:19:23
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
pair<int, int> euclidExtins(int a, int b) {
    if (b == 0) {
        return make_pair(1, 0);
    }
    else {
        pair<int, int> p0 = euclidExtins(b, a % b);
        pair<int, int> p;
        p.first = p0.second;
        p.second = p0.first - (a / b) * p0.second;
        return p;
    }
}
int cmmmdc(int a, int b) {
    int r;
    while (b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main()
{
    int x, y, z;
    int N;
    fin >> N;
    for (int i = 0; i < N; ++i) {
        fin >> x >> y >> z;
        int d = cmmmdc(x, y);
        if (z % d != 0) {
            fout << "0 0\n";
        }
        else {
            pair<int, int> ans = euclidExtins(x, y);
            fout << ans.first * (z / d) << " " << ans.second * (z / d) << "\n";
        }
    }
    return 0;
}