Cod sursa(job #2497105)

Utilizator melutMelut Zaid melut Data 22 noiembrie 2019 04:19:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>


using namespace std;


char const in_file[] = "euclid3.in";
char const out_file[] = "euclid3.out";


ifstream Read(in_file);
ofstream Write(out_file);


inline int32_t GCD(
    int32_t const first,
    int32_t const second,
    int32_t &x,
    int32_t &y
) {
    if (second == 0) {
        x = 1;
        y = 0;
        return first;
    }

    int32_t x0;
    int32_t y0;
    int32_t divisor = GCD(second, first % second, x0, y0);

    x = y0;
    y = x0 - (first / second) * y0;

    return divisor;
}


int main() {
    uint32_t n;
    int32_t a;
    int32_t b;
    int32_t c;
    int32_t x;
    int32_t y;
    int32_t divisor;

    for (Read >> n; n; --n) {
        Read >> a;
        Read >> b;
        Read >> c;

        divisor = GCD(a, b, x, y);

        if (c % divisor) {
            Write << "0 0\n";
        }
        else {
            Write << x * (c / divisor) << ' ';
            Write << y * (c / divisor) << '\n';
        }
    }

    Read.close();
    Write.close();

    return 0;
}