一、逆元定义
若a * x ≡ 1 （mod b），且a和b互质
那么就能定义：x为a的逆元，记为a-1
所以诚x为a在mod b的意义下的倒数
所以对于a/b（mod p）
就可以求b在mod p下的逆元，然后乘上a，再mod p。
二、适用范围
乘法逆元一般用于求 a/b （mod p） 的值
（p通常为质数，也可以不为质数）
三、求解逆元的四种方法
拓展欧几里得
费马小定理
线性递推
阶乘
注：
前两个算法（拓展欧几里得 和 费马小定理）适合求解单个值的逆元 [拓展欧几里得似乎比费马小定理还要好一些]
后两个算法（线性递推 和 阶乘）适合一串数对于一个mod p的逆元 [线性递推大概要比阶乘好一些吧]
四、算法
1.拓展欧几里得
适用范围：a和p互质 p可以不是质数
利用拓展欧几里得求解同余方程 a * x ≡ c (mod b) 当c = 1的情况
转化成解 a * x + b * y = 1 这个方程
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,p;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
x = 1,y = 0;
else
exgcd(b,a%b,y,x),y -= a/b * x;
}
int main()
{
scanf("%lld%lld",&n,&p);
ll x,y;
for(int i = 1; i <= n; i++)
{
x = 0,y = 0;
exgcd(i,p,x,y);
x = (x % p + p)%p;
printf("%lld\n",x);
}
return 0;
}
（按洛谷板子题写的）（tle两个点）
2.费马小定理
咕咕咕（自己的一篇极简题解）
适用范围：a和p互质，p为素数。
根据费马小定理
bp - 1 ≡ 1(mod p)，即 b * bp - 2 ≡ 1 (mod p)
因此，当模数p为质数时，bp - 2即为b的乘法逆元
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,p;
ll qpow(ll a,ll b)
{
a %= p;
ll sum = 1;
while(b)
{
if(b%2 == 0)
a = (a * a)%p,b/=2;
else
sum = (sum * a)%p,b--;
}
return sum % p;
}
int main()
{
scanf("%lld%lld",&n,&p);
for(int i = 1; i <= n - 1; i++)
printf("%lld\n",qpow(i,p - 2));
printf("%lld",qpow(n,p - 2));
return 0;
}
（tle了两个点）
3.线性递推
首先有一个，1-1 ≡ 1（mod p）
然后设p = k * i + r ( 1 < r < i < p)
也就是k是 p / i 的商，r是余数
再讲这个式子放到（mod p）意义下就会得到
k * i + r ≡ 0
然后乘上i-1 ， r-1 就可以得到
k * r-1 + i-1 ≡ 0 (mod p)
i-1 ≡ -k * r-1 (mod p)
i-1 ≡ -(p / i) * (p mod i)-1(mod p)
#include<cstdio>
#define ll long long
using namespace std;
int main()
{
ll n,p;
ll inv[3000005];
scanf("%lld%lld",&n,&p);
inv[1] = 1;
for(ll i = 2;i <= n;i++)
inv[i] = (p - p / i) * inv[p % i] % p;
for(ll i = 1;i <= n;i++)
printf("%lld\n",inv[i]);
return 0;
}
4.阶乘
inv[i + 1] = 1/ (i + 1)!
inv[i + 1] * (i + 1) = 1 / i! = inv[i]
所以我们可以求出n！的逆元，然后逆推，就可以求求出1...n！所有的逆元了
逆推式为
inv[ i + 1 ] * (i + 1)= inv[ i ]
所以我们可以求出任意i,i!,1/i! 的取值了
然后这个也可以导出 1 / i (mod p) 的取值
也就是 1 / i ! * ( i - 1) ! = 1 / i ( mod p )
#include<cstdio>
#define ll long long
using namespace std;
ll n,p;
ll inv[3000005],f[3000005];
ll qpow(ll a,ll b)
{
ll sum = 1;
while(b)
{
if(b%2 == 1)
sum = (sum * a) % p , b--;
else
a = (a * a) % p , b /= 2;
}
return sum;
}
int main()
{
scanf("%lld%lld",&n,&p);
f[0] = 1;
for(int i = 1; i <= n; i++)
f[i] = (f[i - 1] *i) %p;
ll last = qpow(f[n],p - 2);
ll k;
for(ll i = n; i >= 1; i--)
{
k = (last * i) % p;
inv[i] = last * f[i - 1] % p;
last = k;
}
for(int i = 1;i <= n;i++)
printf("%lld\n",inv[i]);
return 0;
}