[笔记]浅谈乘法逆元

发表于 | 阅读次数：

前言

我们知道对于加、减、乘运算来说，取模运算都可以分配进去。而类似于$(a/b)\%mod​$这种式子，如果改成$(a\%mod/b\%mod)\%mod​$则有可能螺旋爆炸。所以我们就要用到逆元。

基本定义

对于一个形似$ax \equiv 1(mod \space p)$的式子，我们称$x$是$a$在$mod \space p$意义下的逆元。记作$x=inv(a)$或$x=a−1$

而对于$a$在$(mod \space p)$意义下存在逆元$x$的必要条件就是$gcd(a,p)=1$，即$a,p$互质。

用途

继续我们在前言中提到的问题。对于$(a/b)\%mod$这种式子，我们不能直接取余。

所以我们就考虑化除为乘。什么意思呢？先假设$x$为$b$的逆元，即$x=b−1$。

有一个基本定理：除以一个数等于乘上这个数的逆元。

所以我们就可以把式子化成$(ax)\%mod$。这样我们就可以开心的直接取余啦O(∩_∩)O。

求法

关于逆元的求法，这里给出$4$种方法，OI中常用。

1. 拓展欧几里得

求解$ax \equiv 1(mod \space p)$这样的方程。

可以等价转化为求解$ax−kp=1$这样的方程。

那么我们就可以套用拓展欧几里得解方程。

但是要注意当且仅当$gcd(a,p)=1$时，才存在$a$在$(mod \space p)$意义下的逆元$x$。

然后我们求解完后把$x$调整到$1 \sim p−1$即可。

这个方法常用于单次求一个逆元。时间复杂度较优。常数较小。

时间复杂度为$O(logN)$

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a,int b,int &x,int &y)
{
	if (!b) {x=1,y=0; return a;}
	int ret=exgcd(b,a%b,y,x);
	y-=x*(a/b); return ret;
}
int inv(int a,int p) //求解ax≡1(mod p)
{
	int x,y;
	return exgcd(a,p,x,y)==1?(x+p)%p:-1; //-1即为不存在逆元
}

2. 费马小定理

先给出费马小定理：$a^{p−1} \equiv 1(mod \space p)$（$p$为质数）

怎么用呢？我们把上面的式子化作$ax \equiv 1(mod \space p)$的形式，就成为了$a \cdot a^{p−2} \equiv 1(mod \space p)$

通过观察我们发现，此时的方程的解$x=a^{p−2}$，然后我们用快速幂求解一下就行了。

这个方法也常用于单次求一个逆元，但只限于$p$为素数的情况。

时间复杂度为$O(log N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int FastPower(int a,int x) //计算a^x
{
	int ret=1,base=a;
    //一般情况下要long long，根据题目意思来判断
	while (x)
	{
		if (x&1) ret=ret*base%mod;
		base=base*base%mod; x>>=1;
	} return ret%mod;
}
int inv(int a,int p)
{
	return FastPower(a,p-2); //求逆元
}

3. 顺序递推法

有的时候题目需要多次用到$1 \sim N$里的逆元，我们就需要在更优的时间内求解出$1 \sim N$的逆元

接下来的2种方法都能实现在$O(N)$的时间复杂度内计算出$1 \sim N$的所有逆元

首先，这种方法还是只适用于$p$为质数的情况。

我们假设现在要求解$i$的逆元，$ix \equiv 1(mod \space p)$。

根据带余除法我们可以得到：$p=ik+r (k=⌊pi⌋)$

那么我们就有：$ik+r \equiv 0(mod \space p)$

注意$p$为质数，所以说$r$的逆元一定存在

由于我们要求$i$的逆元，即求$inv(i)$。所以我们将方程两边同乘$inv(i) \cdot inv(r)$

由于$i \cdot inv(i) \equiv 1(mod \space p)$。那么，方程就变为

$=>k \cdot inv(r)+inv(i) \equiv 0(mod \space p)$

$=>inv(i) \equiv −k \cdot inv(r)(mod \space p)$

$=>inv(i) \equiv −⌊\frac{p}{i}⌋ \cdot inv(p \space mod \space i)(mod \space p)$

$=>inv(i) \equiv (p−⌊\frac{p}{i}⌋) \cdot inv(p \space mod \space i)(mod \space p)$

这样的话就可以由前面推出当前的逆元了。

代码非常简短。

时间复杂度为$O(N)$

1
2
3
inv[1]=1; //注意初始化
for (Re i=2; i<=N; ++i)
	inv[i]=(P-P/i)*inv[P%i]%P;

4. 倒推求阶乘逆元

首先，这种方法又还是只适用于$p$为质数的情况。

这种方法常用在组合数中。证法也比较简单。

我们将$k!$的逆元记作$facinv(k)$。

由于$facinv((k−1)!) \equiv k∗facinv(k!)(mod \space p)$

所以$facinv(k!) \equiv (k+1)∗facinv((k+1)!)(mod \space p)$

这样我们就可以求出$1!∼N!$的逆元。

但是必须先预处理出$N!$的逆元才能倒推回去。

预处理可以选择方法$1、2$中的任意一个

代码也是比较简短的。

时间复杂度为$O(N)$

1
2
3
facinv[N]=FastPower(a,p-2);
for (Re i=N-1; i>=1; --i)
    facinv[i]=(i+1)*facinv[i+1]%p;

这里还可以通过另外的方法再利用$facinv$数组再推算出$1 \sim N$的逆元。

这里就不做说明了，留给读者自己思考。（反正用第3种就好了嘿嘿嘿）

总结&模板题

逆元在OI竞赛中还是算比较常用的知识点了，所以今天特别写了一份比较详细的逆元整理笔记，希望对大家能有帮助O(∩_∩)O。

模板题Luogu P3811

在放上我的代码吧（凑字数(●ˇ∀ˇ●)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <iostream>
#define Re register int

long long N,P,inv[3000005];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	var=w?-x:x;
}
int main(int argc, char const *argv[])
{
	read(N),read(P); inv[1]=1;
	for (Re i=2; i<=N; ++i)
		inv[i]=(P-P/i)*inv[P%i]%P;
	for (Re i=1; i<=N; ++i)
		printf("%lld\n",inv[i]);
	return 0;
}