Extended Euclidean Algorithm - YessineJallouli/Competitive-Programming GitHub Wiki

struct egcd_t{
  ll a,b,g;
};

egcd_t egcd(ll a,ll b)
{
    if(a<b)
    {
        auto e = egcd(b, a);
        std::swap(e.a,e.b);
        return e;
    }
    ll q,s1=1,s2=0,t1=0,t2=1,tmp;
    while(b)
    {
        q=a/b;
        tmp=s2;
        s2=s1-q*s2;
        s1=tmp;
        tmp=t2;
        t2=t1-q*t2;
        t1=tmp;
        tmp=b;
        b=a-b*q;
        a=tmp;
    }
    return {s1,t1,a};
}

pair<ll,ll> bezout(ll a, ll b)
{
    // return u ,v such that au+bv = g and g = gcd(a,b)
    auto [u,v,_]=egcd(a,b);
    return {u,v};
}