Cod sursa(job #2739104)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 6 aprilie 2021 20:28:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 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;

        if(a == 0) {
            if(c % b == 0) {
                fout << "0 " << c / b << '\n';
            }
            else {
                fout << "0 0\n";
            }
        }
        else if(b == 0) {
            if(c % a == 0) {
                fout << c / a << " 0\n";
            }
            else {
                fout << "0 0\n";
            }
        }
        else {
            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;
}