Cod sursa(job #2919503)

Utilizator OvidRata Ovidiu Ovid Data 17 august 2022 20:29:55
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);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
#define int ll


ifstream fin("euclid3.in"); ofstream fout("euclid3.out");
#define cin fin
#define cout fout

int t, a, b, c;
int X1, Y1, x, y;

void euclidExtins(int a, int b, int c){

if(b==0){
    x=c/a; y=0;
}
else{
    euclidExtins(b, a%b, c);
    X1=x; Y1=y;
    x=Y1;
    y=X1-Y1*(a/b);
}
return;
}


int32_t main(){
INIT

cin>>t;

while(t--){
    cin>>a>>b>>c;
    if( (((int)abs(c))%__gcd(abs(a), abs(b) ))>0 ){
        cout<<"0 0\n";
    }
    else{
        euclidExtins(a, b, c);
        cout<<x<<" "<<y<<"\n";
    }
}

return 0;
}