Cod sursa(job #2623677)

Utilizator OvidRata Ovidiu Ovid Data 3 iunie 2020 16:30:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
ifstream fin("euclid3.in"); ofstream fout("euclid3.out");
#define cin fin
#define cout fout
int a, b, c, t;



int euclid(int a, int b, int &x,int &y){


if(b==0){
    x=1; y=0; return a;
}
int x0, y0;
int d=euclid(b, a%b, x0, y0);
x=y0; y=x0-(a/b)*y0;
return d;
}






int32_t main(){
INIT
cin>>t;

for(;t;t--){
    cin>>a>>b>>c;

    if(c%(__gcd(a, b))!=0 ){cout<<"0 0\n"; continue;}

    if(abs(a)<abs(b)){
            swap(a, b);
    int x, y;
    int g=euclid(a, b, x, y);

    cout<<y*(c/g)<<" "<<x*(c/g)<<"\n";
    }
    else{
    int x, y;
    int g=euclid(a, b, x, y);
    cout<<x*(c/(g))<<" "<<y*(c/g)<<"\n";


    }



}

return 0;
}