模意义下的乘法逆元

费马小定理

根据费马小定理

\[a ^ {p - 1} \equiv 1 \pmod{p}\]

容易看出，

\[a ^ {p - 2}\]

即为所求，用快速幂即可。

实现

typedef long long ll;
inline ll qpow(ll a, ll b, ll p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}
inline ll getinv(ll a, ll p)
{
    return qpow(a % p, p - 2, p);
}

扩欧

同余方程

\[ax \equiv 1 \pmod{p}\]

等价于不定方程

\[ax + py = 1\]

用 exgcd 即可。

实现

typedef long long ll;

// solve ax + by = 1
void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
}
inline ll getinv(ll a, ll p)
{
    ll x, y;
    exgcd(a, p, x, y);
    return (x + p) % p;
}

正向递推

首先我们有一个 \(1^{-1} \equiv 1 \pmod{p}\)

然后设 \(p = k * i + r (1 < r < i < p)\)

也就是 \(k\) 是 \(p / i\) 的商，\(r\) 是余数。再将这个式子放到 \(\pmod{p}\) 意义下就会得到：

\[k * i + r \equiv 0 \pmod{p}\]

然后乘上 \(i^{-1},r^{-1}\) 就可以得到：

\[k * r^{-1} + i^{-1} \equiv 0 \pmod{p}\]

\[i^{-1} \equiv -k * r^{-1} \pmod{p}\]

\[i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor * (p \bmod i)^{-1} \pmod{p}\]

于是，我们就可以从前面推出当前的逆元了。

实现

typedef long long ll;
ll inv[10010];
inline void init(ll n, ll p)
{
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (p - p / i) * inv[p % i] % p;
}

阶乘递推

由 \((i + 1)! = i! \times (i + 1)\) 知

\[\begin{aligned} i! &= \frac{(i + 1)!}{i + 1} \\ (i!)^{-1} &= \frac{i + 1}{(i + 1)!} \\ (i!)^{-1} &= (i + 1) \times ((i + 1)!)^{-1} \end{aligned}\]

令 \(ifrac_i\) 为 \(i!\) 模 \(p\) 意义下的乘法逆元，则

\[ifrac_i \equiv (i + 1) \times ifrac_{i + 1} \pmod{p}\]

只要根据前文所述求出 \(n!\) 的逆元，那么对 \(i \in [1, n - 1]\) 就都能 \(O(n)\) 递推求了

另一方面，根据 \(i! = i * (i - 1)!\)，亦有

\[\begin{aligned} i^{-1} &= \frac{(i - 1)!}{i!} \\ &= (i - 1)! \times (i!)^{-1} \end{aligned}\]

因此

\[inv_i \equiv frac_{i - 1} \times ifrac_i \pmod{p}\]

这说明 \(inv_i\) 可以由 \(ifrac_i\) 与 \(frac_{i - 1}\) 直接计算得到