Cod sursa(job #3358322)

Utilizator cKalbfleischcoraline Kalbfleisch cKalbfleisch Data 16 iunie 2026 11:05:29
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 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;
    if(a<b)swap(a,b);
    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);
    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();
    }
}