Cod sursa(job #2739103)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 6 aprilie 2021 20:25:46
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;

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

pair<int, int> pereche_a, pereche_b, pereche_r;

int main() {
    int T;
    fin >> T;

    while(T--) {

        int a, b, c;
        fin >> a >> b >> c;

        pereche_a = {1, 0};
        pereche_b = {0, 1};

        int r = a % b;
        pereche_r = {1, -a/b};

        while(r) {
            a = b;
            pereche_a = pereche_b;

            b = r;
            pereche_b = pereche_r;

            r = a % b; // r = a - [a/b] * b
            pereche_r = {pereche_a.first - (a / b) * pereche_b.first, pereche_a.second - (a / b) * pereche_b.second};
        }

        if(c % b == 0) {
            pereche_b = {pereche_b.first * (c / b), pereche_b.second * (c / b)};

            fout << pereche_b.first << ' ' << pereche_b.second << '\n';
        }
        else {
            fout << "0 0\n";
        }
    }

    fin.close();
    fout.close();

    return 0;
}