Cod sursa(job #2975697)

Utilizator radu.Radu Cristi radu. Data 7 februarie 2023 09:17:50
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

long long cmmdc(long long a, long long b) {
    long long r;
    while (b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

pair<long long, long long> euclidExtins(long long a, long long b) {

    if (b == 0) {
        return make_pair(1, 0);
    }

    if (b != 0) {
        long long r, c;
        r = a % b;
        c = a / b;
        pair <long long, long long> p0 = euclidExtins(b, r);
        long long y = p0.first - c * p0.second;
        long long x = p0.second;
        return make_pair(x, y);
    }
}

int main()
{
    int T;
    long long a, b, c;
    fin >> T;
    for (int i = 0; i < T; ++i) {
        fin >> a >> b >> c;
        long long cm = cmmdc(a, b);
        if (c % cm != 0) {
            fout << "0 0\n";
        }
        else {
            long long x0 = 0, y0 = 0;
            pair<long long, long long> p = euclidExtins(a, b);
            fout << p.first * (c / cm) << " " << p.second * (c / cm) << "\n";
        }
    }
    return 0;
}