Cod sursa(job #2417316)

Utilizator cristina_borzaCristina Borza cristina_borza Data 29 aprilie 2019 15:14:14
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;

ifstream f ("euclid3.in");
ofstream g ("euclid3.out");

long long a, b, c, xa, ya;
int T;

long long EuclidExtins (long long a, long long b, long long &xa, long long &ya) {
    long long x = 0, y = 1, aux = 0;
    xa = 1, ya = 0;

    while (b) {
        long long c = a / b;
        long long r = a % b;

        aux = x; x = xa - c * x; xa = aux;
        aux = y; y = ya - c * y; ya = aux;

        a = b;
        b = r;
    }

    return a;
}

int main() {
    f >> T;
    while (T--) {
        f >> a >> b >> c;
        long long cmmdc = EuclidExtins (a, b, xa, ya);

        if (c % cmmdc == 0)  g << xa * c / cmmdc << " " << ya * c / cmmdc << "\n";
        else g << 0 << " " << 0 << "\n";
    }
}