Cod sursa(job #3358327)

Utilizator cKalbfleischcoraline Kalbfleisch cKalbfleisch Data 16 iunie 2026 11:10:41
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(b==0)return a;
    return gcd(b,a%b);
}

void extGCD(int a, int b, int &va1, int &va2){
    if(b==0){
        va1=1;
        va2=0;
        return;
    }
    int v1,v2;
    extGCD(b,a%b,v1,v2); // v1*b + v2*(a-kb)=x  a%b = a-kb  v1*b + v2*a
    int k=a/b;
    va1=v2;
    va2=v1-k*v2;
}

void solve(){
    int a,b,c;cin>>a>>b>>c;
    bool isW=false;
    if(a<b){swap(a,b);isW=true;}
    int gc=gcd(a,b);
    if(c%gc!=0){cout<<"0 0\n";return;}
    int mult=c/gc;
    int v1,v2;
    extGCD(a,b,v1,v2);
    if(isW){
        swap(v1,v2);
    }
    cout<<v1*mult<<' '<<v2*mult<<'\n';
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    int Q;cin>>Q;
    while(Q--){
        solve();
    }
}