乘法逆元笔记

本人在比赛中经常会忘记怎么写乘法逆元，故此写下这篇笔记，方便自己和其他人查阅。

定义

如果 $ax \equiv 1 \pmod{p}$，则称 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元，记作 $a^{-1}$。

逆元的存在性条件是 $a$ 和 $p$ 互质，既 $\gcd(a,p)= 1$。

用处

乘法逆元在模 $p$ 意义下的除法中起到关键作用。对于 $a$ 和 $b$，如果我们想计算 $\frac{a}{b} \mod p$，可以转化为 $a \cdot b^{-1} \mod p$。

求法

扩展欧几里得算法

扩展欧几里得算法可以用来求解 $ax + by = \gcd(a, b)$ 的整数解。对于模 $p$ 的情况，我们可以设 $b = p$，则有：
$$ax + py = \gcd(a, p)$$

根据逆元的存在条件可知 $\gcd(a, p) = 1$，则有：

$$ax + py = 1$$
从而 $x$ 就是 $a$ 在模 $p$ 意义下的乘法逆元。

代码实现

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;
}

快速幂

如果 $p$ 是质数，可以使用快速幂来求逆元。根据费马小定理，对于质数 $p$，有：

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

因此：

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

所以可以通过快速幂计算 $a^{p-2} \mod p$ 来得到 $a$ 的逆元。

代码实现

int modInverse(int a, int p)
{
    int res = 1;
    a = a % p; // 确保 a 在模 p 意义下
    if (a == 0) return 0; // 如果 a 为 0，则逆元不存在
    int exp = p - 2; // 根据费马小定理
    while (exp > 0)
    {
        if (exp % 2 == 1) // 如果 exp 是奇数
        {
            res = (res * a) % p;
        }
        a = (a * a) % p; // 平方
        exp /= 2; // 除以 2
    }
    return res;
}

注意: 快速幂法使用了费马小定理，要求 $p$ 是质数，如果 $p$ 不是质数，则需要使用扩展欧几里得算法。

预处理逆元

如果需要频繁计算多个数的逆元，可以预处理所有数的逆元。可以使用一个数组 inv，其中 inv[i] 存储 $i$ 在模 $p$ 意义下的逆元。

递推关系为：

$$inv[i] = (p - p / i) \cdot inv[p \mod i] \mod p$$

代码实现

const int MAXN = 1000000; // 根据需要调整大小
int inv[MAXN];
void precomputeInverses(int p)
{
    inv[1] = 1; // 1 的逆元是 1
    for (int i = 2; i < p; ++i)
    {
        inv[i] = (p - p / i) * inv[p % i] % p; // 使用快速幂或扩展欧几里得算法
    }
}