逆元

逆元的诞生是源于除法没有同余定理。

逆元的定义：在模意义下，一个数 $a$ 除以 $b$，等于乘 $b$ 的逆元。

首先我们要知道什么是同余定理。其实就是针对取模的运算的基本原理： 当 $a\equiv b\pmod m,c\equiv d\pmod m,m>0$ 时：

$$a+c\equiv b+d\pmod m\\a-c\equiv b-d\pmod m\\ac\equiv bd\pmod m$$

当 $a\equiv b\pmod m,m>0,k>0$ 时：

$$a^k\equiv b^k\pmod m$$

这时候注意，这些公式里面没有除法，说明除法是不一定满足的。这时就引出了逆元。 逆元其实就是把模意义下的除法变成乘法，对于一个正整数 $a$，它的逆元 $inv$ 与它的乘积在模 $m$ 的意义下为 $1$，也就是 $a\times inv=1\pmod 1$，$inv$ 也可以用 $a^{-1}$ 表示。这个时候就会发现：这个逆元不就是倒数吗？确实是，但是我们是要转换成乘法，倒数还是一个分数，也就是除法，是没什么意义的。

那怎么求 $a$ 的逆元呢，有以下方法。

费马小定理

由费马小定理可知：

$$inv=a^{p-2}\pmod p$$

使用快速幂解决即可，时间复杂度 $O(\log p)$，但是求 $n$ 个数的逆元的复杂度是 $O(n\log p)$，不够快。

线性递推

我们设 $g_x$ 表示 $x!$ 在模 $m$ 意义下的逆元，$f_x$ 表示 $x$ 的阶乘。其中 $x!=\prod^x_{i=1}i$，其实就是 $x$ 的阶乘。

$f_i$ 显然可以用递推 $f_i=f_{i-1}\times i$ 来解决。问题是怎么求解 $g_i$？ 这里给出一个要证明的结论：

$$g_{i-1}=g_i\times i\\\frac{1}{(i-1)!}=\frac{i}{i!}$$

右边的 $i!$ 与 $i$ 消掉变成 $(i-1)!$，所以等式成立。 所以可以先用费马小定理 $O(\log p)$ 的求出 $g_n$，剩下的直接从 $n$ 开始逆推回来。

求出了 $x!$ 的逆元，接下来就是求 $x$ 的逆元。 设 $i$ 的逆元为 $inv_i$，还是给出要证明的结论：

$$inv_i=g_i\times f_{i-1}\\\frac{1}{i}=\frac{1}{i!}\times (i-1)!$$

$i!\times (i-1)!$ 显然等于 $i$，所以等式成立。

这样就可以用线性离线处理出 $1$ 到 $n$ 的逆元了。时间复杂度 $O(n+\log p)-O(1)$。 注意点 1.递推求阶乘时注意 $0!=1$ 这个边界。 2.推阶乘逆元的递推是从大到小。

code

P3811 【模板】模意义下的乘法逆元

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=5e6+10;
ll n;
ll p;
ll qpow(ll a,ll b,ll p){
	ll res=1;
	a%=p;
	while(b){
		if(b&1){
			res=res*a%p;
		}
		a=a*a%p;
		b>>=1;
	}
	return res;
}
ll inv[N];
ll fact[N];
void init(int n){
	fact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=fact[i-1]*i%p;
	}
	int k=qpow(fact[n],p-2,p);
	inv[n]=k;
	for(int i=n;i>=1;i--){
		inv[i-1]=inv[i]*i%p;
	}
	for(int i=1;i<=n;i++){
		cout<<inv[i]%p*fact[i-1]%p<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>p;
	init(n);
	return 0;
}