Cod sursa(job #2461009)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 24 septembrie 2019 20:07:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include<bits/stdc++.h>
#define ll long long
#define a first
#define b second
using namespace std;
ll cmmdc(ll a, ll b){
    ll r;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
/*void aee_fai(ll a, ll b, ll &x, ll &y){
    ll r, q;
    pair<ll,ll> v,v0,v1;
    v0={1,0};//a
    v1={0,1};//b
    while(b!=0){
        q=a/b;
        r=a%b;
        a=b;
        b=r;
        v=v0;
        v0=v1;
        v1.first=v.first-q*v1.first;
        v1.second=v.second-q*v1.second;
    }
    x=v0.first;
    y=v0.second;
}*/
void aee_fai(ll a, ll b, ll&alfa, ll &beta){
    ll c,r;
    pair<ll,ll> v0, v1, v;
    v0.a=1; v0.b=0;
    v1.a=0; v1.b=1;
    while(b!=0){
        c=a/b;
        r=a%b;
        a=b;
        b=r;

        v=v0;
        v0=v1;
        v1.a=v.a-c*v1.a;
        v1.b=v.b-c*v1.b;
    }

    alfa=v0.a;
    beta=v0.b;
}
void solve(){
    ll a, b, c, x, y, gcd;
    cin>>a>>b>>c;
    gcd=cmmdc(a,b);
    if(c%gcd!=0) cout<<0<<' '<<0<<"\n";
    else{
        aee_fai(a, b, x, y);
        ll val=c/gcd;
        cout<<val*x<<' '<<val*y<<"\n";
    }
}
int main()
{
    int nrt;
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    cin>>nrt;
    while(nrt--)
        solve();
    return 0;
}