$a,b\in\mathbb{Z}$，且 $ab \equiv 1 \pmod{n}$，则称 $a$ 和 $b$ 关于模 $n$ 互为模逆元（Modular Multiplicative Inverse）

还可记作：$b \equiv \frac{1}{a} \pmod{n}$ 或 $b \equiv a^{-1} \pmod{n}$

模运算的部分性质

$(a+b)\bmod n=(a\bmod n+b\bmod n)\bmod n$

$(a-b)\bmod n=(a\bmod n-b\bmod n+n)\bmod n$

$(a\cdot b)\bmod n=((a\bmod n)\cdot (b\bmod n))\bmod n$

$a^b\bmod n=(a\bmod n)^b\bmod n$

上面三条性质，相当于加、减、乘、乘方都齐了，那么除呢？$\frac{a}{b}\bmod n=\ ?$

这就需要模逆元来解决。

模逆元

类比倒数 $a\cdot b=1$， $ab \equiv 1 \pmod{n}$ 也可以称它们互为模倒数（模逆元）

那么如果知道 $b$ 的模逆元为 $x$， $\frac{a}{b}\bmod c$ 就可以转化为 $(a\cdot x) \bmod c$

求法

费马小定理 (Fermat's Little Theorem)

若 $p$ 为质数，整数 $a$ 与 $p$ 互质，则 $a^{p-1}\equiv 1\pmod p$

另一种形式：对于任意整数 $a$，有 $a^p\equiv a\pmod p$

由以上定理：

$a^{p-1}\equiv 1\pmod p$

左边提出一个 $a$：

$a\cdot a^{p-2}\equiv 1\pmod p$

因此可得出：

$a^{-1}\equiv a^{p-2}\pmod p$

因此 $a$ 关于模 $p$ 的逆元就是 $a^{p-2}\bmod p$。

例如要求 $(15/5)\bmod 4$，就先求 $5$ 关于 $4$ 的逆元 $5^{4-2}\bmod 4=25\bmod 4=1$，然后就可以转化为 $(15/5)\bmod 4=(15\cdot 1)\bmod 4=3$

注意：

  • 满足整数 $a$ 与 $p$ 互质，才存在逆元，否则逆元不存在。
  • $p$ 为质数才可使用费马小定理计算逆元，否则需要使用扩展欧几里得算法求逆元。

快速幂

在实际题目中，模 $p$ 往往非常大，比如为 $20220211$，那要求一个数的模逆元就会进行一个很大指数运算，因此为了节省时间需要使用快速幂。同时快速幂也兼容取模，因此可以在算幂的同时进行取模运算。

#define MOD 20220211
long long fastpow(long long a, long long b)
{
    a %= MOD; // 开头先取一次模
    long long ans = 1;
    while (b)
    {
        if (b % 2 == 1)
            ans = ans * a % MOD; // 每次运算都取模
        a = a * a % MOD; // 每次运算都取模
        b >>= 1;
    }
    return ans;
}