数论 | 模逆元

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

还可记作：$b\equiv \frac{1}{a}(\mathrm{mod}n)$ 或 $b\equiv a^{-1}(\mathrm{mod}n)$

模运算的部分性质

$(a+b)modn=(amodn+bmodn)modn$

$(a-b)modn=(amodn-bmodn+n)modn$

$(a\cdot b)modn=((amodn)\cdot (bmodn))modn$

$a^{b}modn=(amodn{)}^{b}modn$

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

这就需要模逆元来解决。

模逆元

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

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

求法

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

若 $p$ 为质数，整数 $a$ 与 $p$ 互质，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$

另一种形式：对于任意整数 $a$，有 $a^p\equiv a(\mathrm{mod}p)$

由以上定理：

$a^{p-1}\equiv 1(\mathrm{mod}p)$

左边提出一个 $a$：

$a\cdot a^{p-2}\equiv 1(\mathrm{mod}p)$

因此可得出：

$a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$

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

例如要求 $(15/5)mod4$，就先求 $5$ 关于 $4$ 的逆元 $5^{4-2}mod4=25mod4=1$，然后就可以转化为 $(15/5)mod4=(15\cdot 1)mod4=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;
}