Cod sursa(job #2528393)

Utilizator leru007Leru Ursu leru007 Data 21 ianuarie 2020 20:29:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t;
ll a,b,c;
ll gcd(ll a,ll b,ll &X,ll &Y){
    if(b==0){
        X=1;
        Y=0;
        return a;
    }
    else{
        ll X0=0,Y0=0,D=0;
        D=gcd(b,a%b,X0,Y0);
        ll tz=X0;
        X=Y0;
        Y=(X0-(a/b)*Y0);
        return D;
    }
}
int32_t main() {
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    fin>>t;
    while(t--){
        fin>>a>>b>>c;
        ll x=0,y=0;
        ll ans=gcd(a,b,x,y);
        if(c%ans!=0){
            fout<<0<<" "<<0<<"\n";
        }
        else{
            fout<<x*(c/ans)<<" "<<y*(c/ans)<<"\n";
        }
    }
    return 0;
}