逆元

扩展欧几里得法求逆元

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

快速幂法求逆元

因为 $ax \equiv 1 \pmod b$ ；

所以 $ax \equiv a^{b-1} \pmod b$ （根据 费马小定理 ）；

所以 $x \equiv a^{b-2} \pmod b$ 。

线性求逆元

求出 $1,2,...,n$ 中每个数关于 $p$ 的逆元。

首先，很显然的 $1^{-1} \equiv 1 \pmod p$ ；

然后，设 $p=ki+j,j<i,1<i<p$ ，再放到 $\mod p$ 意义下就会得到： $ki+j \equiv 0 \pmod p$ ；

两边同时乘 $i^{-1},j^{-1}$ ：

$kj^{-1}+i^{-1} \equiv 0 \pmod p$ ；

$i^{-1} \equiv -kj^{-1} \pmod p$ ；

$i^{-1} \equiv -(\frac{p}{i}) (p \bmod i)^{-1}$ ；

inv[i] = 1;
for (int i = 2; i <= n; i++) {
    inv[i] = (ll)(p - p / i) * inv[p % i] % p;
}