专栏文章

【x义x讲坛】浅谈模质数意义下的乘法逆元

xx义x
算法·理论参与者 56已保存评论 64

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
64 条
当前快照
1 份
快照标识符
@mhz5sbyf
此快照首次捕获于
2025/11/15 01:55
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文
『菜鸡的blog』\color{green}\Large\texttt{『菜鸡的blog』}
我们直接切入正题吧。

问题一：什么是乘法逆元呢？

简单来说就是这样：在(modp)\pmod p意义下，如果a∗a′≡1a*a' \equiv 1，那么我们就说a′a'是aa的逆元。当然啦，反过来，aa也是a′a'的逆元。
（如果a,pa,p不互质的话aa是没有逆元的）
（在pp不是素数的时候情况比较复杂，所以这一篇先介绍pp为素数时的情况）

问题二：逆元有什么性质？

逆元的性质可真是多了去了，比较重要的有一下几个：
（在这些性质中，一般都有一个特例：0，所以我们就不谈a=0a=0的情况了）

1.存在唯一性

对于aa来说，它只会有一个，且一定有一个逆元。
这是为什么呢？
我们先假设aa有两个不相等逆元：a′a'和a′′a''，那么一定有：
a∗a′≡a∗a′′≡1(modp)a*a'\equiv a*a''\equiv1\pmod p
不妨设a′<a′′a'<a''且a′′−a′=ka''-a'=k，那么
a∗(a′′−k)≡a∗a′′(modp)a*(a''-k)\equiv a*a'' \pmod p
a∗a′′−a∗k≡a∗a′′(modp)a*a''-a*k\equiv a*a''\pmod p
a∗k≡0(modp)a*k\equiv0\pmod p
由于a≠0a\neq 0，所以k≡0(modp)k\equiv 0\pmod p，即a′≡a′′a'\equiv a''，与假设矛盾，所以aa只能有一个逆元。
至于逆元的存在性，读者自己思考一下吧。（就是你懒！）

2.完全积性函数

为了接下来方便，我们把aa的逆元表示为inv[a]inv[a]吧。
这个性质是说：
两个数的逆元的积等于这两个数积的逆元，inv[a]∗inv[b]≡inv[a∗b]inv[a]*inv[b]\equiv inv[a*b]。
这点也不难证：
显然
a∗inv[a]≡b∗inv[b]≡1(modp)a*inv[a]\equiv b*inv[b]\equiv 1 \pmod p
那么
a∗inv[a]∗b∗inv[b]≡1∗1(modp)a*inv[a]*b*inv[b]\equiv1*1 \pmod p
所以
(a∗b)∗(inv[a]∗inv[b])≡1(modp)(a*b)*(inv[a]*inv[b])\equiv1 \pmod p
这不就是(a∗b)(a*b)的逆元的定义吗！

3.a∗inv[b]≡a/ba*inv[b]\equiv a/b (modp)\pmod p

显然
b∗inv[b]≡1(modp)b*inv[b]\equiv 1 \pmod p
两边都乘以aa得
a∗b∗inv[b]≡a(modp)a*b*inv[b]\equiv a \pmod p
也就是
a∗inv[b]≡a/b(modp)a*inv[b]\equiv a/b \pmod p
这个结论非常重要！
有时候我们需要算出a/ba/b modmod pp的值，用朴素的方法，我们只能在aa上不断加pp，直到它能被bb整除为止。当a,b,pa,b,p都很大的时候，这种方法就只能凉凉了，但如果有了逆元，我们就可以非常方便，快捷地求解。

4.卖个关子

不要打我

问题三：逆元怎么求呢？

嗯，逆元确实不错，但怎么求呢？

（单个）求法一：枚举法

枚举kk，检查是否满足a∗k≡1a*k\equiv1 (modp)\pmod p。
太蠢了……

（单个）求法二：费马小定理

费马小定理：当pp为素数时，ap−1≡1a^{p-1}\equiv1 (modp)\pmod p。
那么a∗ap−2≡1a*a^{p-2}\equiv1 (modp)\pmod p。
再看看，这是不是又是逆元的定义？快速幂求出ap−2a^{p-2}即可。

（单个）求法三：扩展欧几里得

寻找a∗x≡1a*x\equiv1 （modmod pp）的解inv[a]inv[a]其实就相当于寻找方程a∗x+p∗y=1a*x+p*y=1的解。
再一看：a,pa,p一定互质，这不就是扩展欧几里得算法的标准形式吗！

（批量）求法四：欧拉筛

刚才讲的都是求单个aa的逆元，但如果我们要求出11~p−1p-1所有数的逆元呢？
还记得逆元是完全积性函数吗？所以对于每个合数aa，我们把所有它的因子的逆元筛出来再相乘即可。
所以我们可以直接把所有素数筛出来，对它们求逆元（二或三），再把它的逆元乘给它的倍数就可以了。
代码如下：（这里用的是快速幂，貌似扩欧比它更快）
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=25000528;
int p,n;
int vis[N],pri[N];
int inv[N];
int mi(int i,int j)  //分治快速幂
{
    if (!j) return 1;
    long long now=mi(i,j>>1);
    now=now*now%p;
    if (j&1) now=now*i%p;
    return (int)now;
}
int main()
{
    cin>>n>>p;
    vis[1]=1,inv[1]=1;
    for (int i=2;i<=p-1;i++)
    {
        if (!vis[i]) pri[++pri[0]]=i,inv[i]=mi(i,p-2);
        for (int j=1;j<=pri[0];j++)
        {
            if (i*pri[j]>=p) break;
            inv[i*pri[j]]=inv[i]*inv[pri[j]];
            if (i%pri[j]==0) break;
        }
    }
    for (int i=1;i<=n;i++)
    printf("%d\n",inv[i]);
    return 0;
}
不能过P3811……换成扩欧可能有救。

求法五：线性递推

现在我们要求kk的逆元。
令a∗k+b=pa*k+b=p。
b∗inv[b]≡1(modp)b*inv[b]\equiv1 \pmod p
把bb换种表达，p−a∗kp-a*k：
(p−ak)∗inv[b]≡1(modp)(p-ak)*inv[b]\equiv1 \pmod p
那么
p∗inv[b]−a∗k∗inv[b]≡1(modp)p*inv[b]-a*k*inv[b]\equiv1 \pmod p
在(modp)\pmod p意义下p≡0p\equiv0，则
−a∗k∗inv[b]≡1(modp)-a*k*inv[b]\equiv1 \pmod p
观察ak+b=pak+b=p，我们发现：a=p/k,b=p%ka=p/k,b=p\% k（除号指整除），则最终
−(p/k)∗inv[p%k]∗k≡1(modp)-(p/k)*inv[p \% k]*k\equiv1 \pmod p
即
−(p/k)∗inv[p%k]≡inv[k](modp)-(p/k)*inv[p\%k]\equiv inv[k] \pmod p
神奇吧~
这就得出了性质4，也是我们今天最后一个求法线性递推的原理了。
这个东西可以以线性递推的方式求11至nn所有数的逆元，也可以以递归的方式求单个数的逆元。（不过似乎和exgcd一样也是辗转相除？）
实际使用的时候记得加上pp来去掉负号。代码如下：（可过P3811）
CPP
#include<bits/stdc++.h>
using namespace std;

int N,p;
int inv[25000528];

int main()
{
	cin>>N>>p;
	inv[1]=1;
	for (int i=2;i<=N;i++)
	inv[i]=(long long)(p-p/i)*inv[p%i]%p;
	for (int i=1;i<=N;i++) printf("%d\n",inv[i]);
	return 0;
}

【谢谢观看】

后记

感觉好多东西都没写到啊……
还有，建议这一篇的各个式子再消化一下。毕竟，一下子来这么多数学公式确实很难接受。

后记的后记（2019/8/6）

本次博客第一次大改。主要是标题字体字号修得更适合阅读，以及LaTeX\LaTeX的问题，然后在开头放了一个本人博客的链接。
不知道你们有没有发现之前本博客的居中是拿\quad拼出来的……然后看看大概是中间位置就算居中了……
怎么莫名感觉之前的自己比现在强呢

评论

共 64 条评论，欢迎与作者交流。

正在加载评论...