Cod sursa(job #3357694)

Utilizator dragos_22Dragos-Radu Stiuca dragos_22 Data 12 iunie 2026 21:40:23
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>

using namespace std;

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


int main(){
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);

    int t;
    cin >> t;
    for(int i = 0;i < t; ++i){
        int a,b,c,x,y,d;
        cin >> a >> b >> c;

        euclidExtins(a,b,&d,&x,&y);
        //cout << d << " " << x << " " << y << '\n';
        
        if(c % d == 0){
            int k = c/d;
            cout << x * k << " " << y * k << "\n"; 
        }
        else
            cout << 0 << " " << 0 << '\n';
    }

    return 0;
}