Cod sursa(job #2772397)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 1 septembrie 2021 00:32:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <list>
#include <utility>

using namespace std;

bool areParticularCases(const long long A, const long long B,
            const long long C, ofstream &out) {
    if (A == 0LL) {
        if (B != 0LL && C % B == 0LL)
            out << 1 << ' ' << C / B << '\n';
        else
            out << "0 0\n";

        return true;
    } else if (B == 0LL) {
        if (A != 0LL && C % A == 0LL)
            out << 1 << ' ' << C / A << '\n';
        else
            out << "0 0\n";

        return true;
    }
    return false;
}

void euclid3(const long long A, const long long B, const long long C,
            ofstream &out) {
    if (areParticularCases(A, B, C, out))   
        return;

    long long a = A, b = B;
    list<pair<long long, long long>> coefStack;

    while (b) {
        coefStack.push_back({a, b});
        long long temp = a;
        a = b;
        b = temp % b;
    }
    long long d = a;

    if (C % d) {
        coefStack.clear();
        out << "0 0\n";
        return;
    }

    long long x1 = 1LL, y1 = 0LL;
    long long x, y, q;

    while (!coefStack.empty()) {
        auto &cf = coefStack.back();
        coefStack.pop_back();
        a = cf.first;
        b = cf.second;
        q = a / b;

        x = y1;
        y = x1 - q * y1 * 1LL;

        x1 = x;
        y1 = y;
    }

    long long fact = C / d;
    x *= fact;
    y *= fact;

    out << x << ' ' << y << '\n';
}

int main(void) {
    ifstream in("euclid3.in");
    ofstream out("euclid3.out");

    int t, a, b, c;
    in >> t;

    for (int i = 0; i < t; i++) {
        in >> a >> b >> c;
        euclid3(a, b, c, out);
    }

    in.close();
    out.close();
    return 0;
}