Cod sursa(job #3344544)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 2 martie 2026 11:52:59
Problema Algoritmul lui Euclid extins Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
#endif

static inline void EuclidExtins(int a, int b, int& d, int& x, int& y) {
    if(b == 0) {
        x = 1;
        y = 1;
        d = a;
    }
    else {
        int x1, y1;
        EuclidExtins(b, a % b, d, x1, y1);
        x = y1;
        y = x1 - (a / b) * y1;
    }
}

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int t;
    fin >> t;
    while(t--) {
        int a, b, c;
        int d, x, y;
        fin >> a >> b >> c;
        EuclidExtins(a, b, d, x, y);

        if(0 != c % d) fout << "0 0\n";
        else fout << x * (c / d) << ' ' << y * (c / d) << '\n';
    }

    return 0;
}