其实比较简单

定义

在数论中，若 $ab \equiv 1\pmod p$ ，我们就称 $a,b$　在模 $p$ 意义下互为乘法逆元，记为 $a=inv(b) \pmod p $ 或 $a=b^{-1} \pmod p$ 。

用途

逆元有什么用？我们常常遇到一些题目要求结果对一个大质数 $p$ 取模，这是因为答案很大，出题人为了不麻烦大家写高精，就采取这样的方法。加减法和乘法对取模运算都是封闭的，所以你可以处处取模来避免溢出。如：

加法：
$12%10=2$
$3%10=3$
$(12+3) % 10=(2+3)%10=5$
乘法：
$12%10=2$
$3%10=3$
$(12 \times 3) %10=(2 \times 3) %10=6$

但遇到除法时，就麻烦了：

除法：
$12%10=2$
$3%10=3$
$(12/3) %10=4 \ne(2/3)%10$

那咋办？逆元啊！看看定义式： $a=inv(b)=b^{-1} \pmod p$ ，这里明白的告诉你了： $a$ 就是模 $p$ 意义下的 $\frac{1}{b}$ 啊！故除法可以这样计算：

除法：
$12%10=2$
$3%10=3$
$(12/3) %10=(12 \times \frac{1}{3}) %10=(2 \times inv(3))%10=4$

妙啊，dalao们的智慧真是无穷的！

计算逆元

拓展欧几里得

这种方法在拓展欧几里得已经介绍了，那道“同余方程”其实就是在求逆元。实际上，这就是最常用的求逆元的方法。代码如下：

LL exgcd(LL a,LL b,LL& x,LL& y){		
	if(!b){	
		x=1,y=0;
		return a;
	}
	LL d=exgcd(b,a%b,y,x);		 
	y-=a/b*x;	
	return d;
}
LL inv(LL a,LL p){ //求a在模p下的逆元 
	LL x,y;
	return exgcd(a,p,x,y)==1?(x%p+p)%p:-1;	//-1表示无解 
}

费马小定理

若 $p$ 为质数，则有 $a^p \equiv a \pmod p$

证明：
费马小定理是欧拉定理的特殊情况，
欧拉定理 $a^{\varphi(n)} \equiv 1 \pmod n$ ，其中 $gcd(a,n)=1$ ，$\varphi(n)$ 为欧拉函数

当 $gcd(a,p)=1$ 时，由欧拉定理 $a^{p-1} \equiv 1 \pmod p$ 两边同时乘 $a$ 得 $a^p \equiv a \pmod p$
当 $gcd(a,p)\ne 1$ 时， $a$ 只能是 $p$ 的倍数，定理显然成立

证毕

那么由逆元的定义推导：
$a\times inv(a)\equiv 1 \equiv a^{p-1} \pmod p$ ，这里 $gcd(a,p)=1$
于是有 $inv(a) = a^{p-2} \pmod p$
So，只要求下快速幂即可，注意这个方法只对 $p$ 是质数的情形有效，代码：

LL qpow(LL a,LL n,LL p){
    LL ans = 1;
    while (n){
        if(n&1) ans=ans%p*a%p;
        a=a%p*a%p;
        n>>=1;
    }
    return ans;
}
LL inv(LL a,LL p){
    return qpow(a,p-2,p);
}

线性递推

以上两种方法都是常用的求逆元方法，但是，洛谷P3811的毒瘤模板题，必须要用特殊的方法

因为这道题要求一系列的乘法逆元，而且数据范围有点大，常规方法是行不通的。这里介绍逆元的线性递推求法（需保证 $p$ 是质数）。

设 $p=aq+r$ ，且 $q=\left \lfloor \frac{p}{a} \right \rfloor$ ， $r= p \bmod a$
在模 $p$ 意义下，有 $(aq+r) \equiv 0 \pmod p$
移项得 $aq=-r\pmod p$
把 $q$ 换成逆元 $a=-r \times inv(q) \pmod p$
再两边变逆元 $inv(a)=-inv(r) \times q\pmod p$
即 $inv(a)= -\left \lfloor \frac{p}{a} \right \rfloor \times inv(p \bmod a) \pmod p$

我们可以用记忆化搜索的方法，减少多次查询的时间复杂度（空间换时间）。（递推亦可，其实就这题而言递推更好）

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3000000+5;
LL inv[N];
int main(){
	LL n,p;
	scanf("%lld%lld",&n,&p);
	inv[0]=0;
	inv[1]=1;
	printf("1\n");
	for(int i=2;i<=n;++i){
		inv[i]=p-(p/i)*inv[p%i]%p;
		printf("%lld\n",inv[i]);
	}	
	return 0;
}

阶乘逆元法

再补充一张用阶乘求逆元的方法，只适用于模数为质数的情况

设 $f(i)=inv(i!),g(i)=i!$
则有： $f(i-1)=f(i) \times i$
证明： $f(i-1)= \frac{1}{(i-1)!}=\frac{1}{i!} \times i=f(i) \times i$

若我们要求 $[1,n]$ 中所有数的的逆元，可以先求 $[1,n]$ 每个数的阶乘的，再用费马小定理求得 $f(n)$ ，之后地推出 $f(1\sim n)$ 但是这还不是我们要的答案啊

dalao又说： $inv(i)=inv(i!) \times (i-1)!$
证明思路同上

So， $inv(i)=f(i) \times (i-1)!$