smart_toy AI 生成摘要
本文笔记整理了乘法逆元的定义、存在条件及主要求法。介绍了基于扩展欧几里得算法的通法,以及基于费马小定理在模数为质数时的快速幂快速求解法。同时讲解了针对大规模数据需求的预处理递推方法,并强调了不同算法对模数性质的依赖,旨在帮助理解并快速查阅。

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

定义

如果 ax≡1(modp)ax \equiv 1 \pmod{p},则称 xx 为 aa 在模 pp 意义下的乘法逆元,记作 a−1a^{-1}。

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

用处

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

求法

扩展欧几里得算法

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

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

ax+py=1ax + py = 1 从而 xx 就是 aa 在模 pp 意义下的乘法逆元。

代码实现

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

快速幂

如果 pp 是质数,可以使用快速幂来求逆元。根据费马小定理,对于质数 pp,有:

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

因此:

ap−2≡a−1(modp)a^{p-2} \equiv a^{-1} \pmod{p}

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

代码实现

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

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

预处理逆元

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

递推关系为:

inv[i]=(p−p/i)⋅inv[pmod  i]mod  pinv[i] = (p - p / i) \cdot inv[p \mod i] \mod p

代码实现

C++
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; // 使用快速幂或扩展欧几里得算法
    }
}