Cod sursa(job #2844071)

Utilizator OvidRata Ovidiu Ovid Data 3 februarie 2022 18:23:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 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


int t, a, b, c;


pair<int, int> euclid_extins(int a, int b){

int x=0, y=0;

if(b==0){
    return make_pair(1, 0);
}

//pr=(x1, y1);
pair<int, int> pr=euclid_extins(b, a%b);
int x1=pr.ft, y1=pr.sc;
x=y1;
int k=a/b;
y=x1-k*y1;
return make_pair(x, y);
}


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

int32_t main(){
INIT

cin>>t;

while(t--){
    cin>>a>>b>>c;
    if(abs(a)<abs(b) ){
        swap(a, b);

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

    pair<int, int> pr=euclid_extins(a, b);
    int x,y;
    x=pr.ft, y=pr.sc;
    x*=c/d;
    y*=c/d;
    cout<<y<<" "<<x<<"\n";


    }
    else
    {

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

    pair<int, int> pr=euclid_extins(a, b);
    int x,y;
    x=pr.ft, y=pr.sc;
    x*=c/d;
    y*=c/d;
    cout<<x<<" "<<y<<"\n";

    }

}


return 0;
}