Cod sursa(job #2281808)

Utilizator I_am_not_a_robotMr Domino I_am_not_a_robot Data 12 noiembrie 2018 19:26:37
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;

using namespace std;

const string FILENAME="euclid3";

/// #define int long long
#define OpenIN() freopen((FILENAME+".in").c_str(),"r",stdin)
#define OpenOUT() freopen((FILENAME+".out").c_str(),"w",stdout)
#define OpenALL() OpenIN(), OpenOUT()
#define infoarena() OpenALL()

ll d;

pair<ll,ll>euclid(ll a,ll b)
{
    if(b==0)
    {
        d=a;
        return {1,0};
    }
    pair<ll,ll>vx=euclid(b,a%b);
    return {vx.second,vx.first-(a/b)*vx.second};
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    infoarena();
    int t;
    cin>>t;
    while(t--)
    {
        ll a,b,x;
        cin>>a>>b>>x;
        pair<ll,ll>g=euclid(a,b);
        if(x%d==0)
        {
            cout<<g.first*(x/d)<<" "<<g.second*(x/d)<<"\n";
        }
        else
        {
            cout<<"0 0\n";
        }
    }
    return 0;
}
/**



**/