扩展欧几里得和逆元

转载自https://www.cnblogs.com/zjp-shadow/p/9267675.html/
给定 $a$ , $b$ , $c$ 都是自然数，求满足方程 $ax+by=c$ 的一组解 $(x,y)$ ，使得 $x$ 非负且最小。
由代数结构，要想有解必须满足 $(a,b)|c$ ，而且 $(a,b)=(b,a\%b)$ 。
所以有朴素的欧几里得：

ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);
}

时间复杂度： $O(loga)$
对于 $ax+by=c$ ，两边同除 $(a,b)$ ，得：
$\frac{a}{(a,b)}x+\frac{b}{(a,b)}y=\frac{c}{(a,b)}$ 。
因为 $\frac{a}{(a,b)}$ 和 $\frac{b}{(a,b)}$ 互质，所以问题转化为新的方程 $ax+by=c,(a,b)=1$ 。
先求解 $ax+by=(a,b)=1$ ，再把 $x,y$ 同乘 $c$ 即可。
又由欧几里得算法，若 $(x,y)$ 满足 $ax+by=(a,b)$ ， $(x',y')$ 满足 $bx'+(a\%b)y'=bx'+(a-a/b*b)y'=(b,a\%b)$ ，由 $(a,b)=(b,a\%b)$ 比较系数知：
$x=y',y=x'-a/b*y'$ ，即问题 $exgcd(a,b,x,y)$ 转移成了问题 $exgcd(b,a\%b,x',y')$ ，然后再令 $x=y',y=x'-a/b*y'$ 即可。
递归出口： $b=0$ 时，有 $ax=1$ ，如果有解，只能是 $a=1,x=1$ ，令 $y=0$ 。
扩展欧几里得：

void exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

这样求得的是一组特解，若要求 $x$ 的非负最小解，只需令 $x=((x\%b)+b)\%b$ 即可。
逆元：
$ax≡1(modb)$ ，则称 $x$ 是 $a$ 模 $b$ 的逆元。这个模等式可以转化成 $ax=by+1$ ，可以用扩展欧几里得求最小非负 $x$ 。
对于一般的 $ax≡c(modb)$ 只要把逆元乘 $c$ 再模b即可。