说在前面

在某些组合数的计数问题中，经常会用到逆元，这里我们讲一下如何线性求出1到n在模p意义下的逆元，注意p为质数。

进入正题

假设我们当前要求a在模p意义下的逆元。
令p=ak+r,(0≤r<a)" role="presentation">p=ak+r,(0≤r<a)$p=ak+r,(0\le r<a)$，那么
ak+r≡0(modp)" role="presentation">ak+r≡0(modp)$ak+r\equiv 0(\mathrm{mod}p)$，然后恒等式变形，两边同时乘a−1×r−1" role="presentation">a−1×r−1$a^{-1}\times r^{-1}$，
则有a−1+kr−1≡0(modp)" role="presentation">a−1+kr−1≡0(modp)$a^{-1}+k{r}^{-1}\equiv 0(\mathrm{mod}p)$，移项
既得a−1≡−kr−1(modp)" role="presentation">a−1≡−kr−1(modp)$a^{-1}\equiv -k{r}^{-1}(\mathrm{mod}p)$，就有
a−1≡−[pa]×(pmoda)−1(modp)" role="presentation">a−1≡−[pa]×(pmoda)−1(modp)$a^{-1}\equiv -[\frac{p}{a}]\times (p\mathrm{mod}a{)}^{-1}(\mathrm{mod}p)$，又因为我们知道与-x同余其实就是等于说与p-x同余，比如说
7≡−3≡5−3≡2(mod5)" role="presentation">7≡−3≡5−3≡2(mod5)$7\equiv -3\equiv 5-3\equiv 2(\mathrm{mod}5)$。
代码： var inv:Array[0..1000] of longint; i,n,p:longint; begin readln(n,p); inv[1]:=1; for i:=2 to n do begin inv[i]:=inv[p mod i]*(p-p div i) mod p; end; for i:=1 to n do write(inv[i],' '); end. 当然。你喜欢也可以写成这样： var inv:array[0..1000] of longint; i,n,p:longint; begin readln(n,p); inv[1]:=1; for i:=2 to n do begin inv[i]:=(-inv[p mod i]*(p div i) mod p+p) mod p; end; for i:=1 to n do write(inv[i],' '); end. 接下来求（1-n）！逆元，由于过于简单，直接上代码 #include #include typedef long long ll; const ll mo=1e+9+7; const int N=2000000; using namespace std; ll fac[N+55],inv[N+56]; ll power(ll a,int b) { ll t=1ll,y=a%mo; while (b) { if (b&1) t=1ll*t%mo*y%mo; y=1ll*y%mo*y%mo; b=b/2; } return t%mo; } int main() { fac[0]=1; for(int i=1;i<=N;i++) fac[i]=fac[i-1]%mo*1ll*i%mo; inv[N]=power(fac[N],mo-2)%mo;//费马小定理暴力求 for(int i=N-1;i>=0;i--) inv[i]=inv[i+1]%mo*(i+1)%mo;//乘上i+1那么前面的部分不就变为1了吗。 }

the end

由于我的水平有限，难免会有些写错的地方，希望大家批评指正，多多包容，thank you for your patience.