模板 - 数学 - 数论 - 扩展欧几里得算法

//扩展欧几里得算法：返回 g=gcd(a,b) ，以及对应的等式 ax+by=g 的解
ll exgcd(ll a,ll b,ll &x,ll &y) {
    if(!a&&!b)
        return -1;
    if(!b) {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

//扩展欧几里得算法求逆元，只要求 a,m 互质
ll inv2(ll a,ll m) {
    ll x,y;
    ll d=exgcd(a,m,x,y);
    if(d==1)
        return (x%m+m)%m;
    return -1;
}