AI 生成摘要
本文介绍了模 $p$ 下水调乘法的定义与存在性，重点讲解了三种求法。方法一利用扩展欧几里得算法求解，适用于任意 $a, p$ 互质的情况；方法二是基于费马小定理的快速幂法，仅适用于 $p$ 为质数；方法三通过递推公式预处理逆元，适合频繁计算需求。文章还附带了相应的代码实现，是数论相关的实用总结。

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

定义

如果 $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$ 意义下的乘法逆元。

代码实现

1
2
3
4
5
6
7
8
9
10
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$ 的逆元。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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$$

代码实现

1
2
3
4
5
6
7
8
9
10
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; // 使用快速幂或扩展欧几里得算法
    }
}