Cod sursa(job #3311844)

Utilizator raul41917raul rotar raul41917 Data 24 septembrie 2025 16:56:48
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

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

void euclidExtended(int a, int b, int d,int *div, int *x, int *y){
    if(b == 0) {
        *div = a;
        *x = 1;
        *y = 0;
    }else{
        int x0, y0;
        euclidExtended(b, a % b, d, div, &x0, &y0);
        *x = y0;
        int c = (a / b);
        *y = (x0 - c * y0);
    }
}

int main(){

    int tests;
    fin >> tests;

    for(int test = 0; test < tests; test++){
        int a, b, d;
        int x, y, div;

        fin >> a >> b >> d;
        euclidExtended(a, b, d, &div, &x, &y);

        if(d % div != 0)
            fout << 0 << " " << 0 << endl;
        else
            fout << x * (d / div) << " " << y * (d / div) << endl;
    }

    return 0;
}