一、什么是逆元
当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有b*c≡1(mod m)；
则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);
即a/b的模等于a*b的逆元的模；
逆元就是这样应用的；
二、求逆元的方法
那么逆元怎么求 ? 首先这里得纠正一点, 我们不能直接说一个数的逆元是多少,
应该这么说: 一个数 x 在模 p的条件下的逆元是多少.(这点概念还是蛮重要的)
其次,我们不难得知一个数的逆元有无穷多个,但是我们只需要求得一个数的最小正整数逆元就行了
另外,一个数 x 在模 p 的条件下不一定有逆元, x关于 p 的逆元存在 当且仅当 x 和 p 互质
这里有一个推导: （设 a 为 x的逆元, b 为任意整数）
x∗a≡1(mod p)= 将p连入式子=> x∗a=1−b∗p => x∗a+b∗p=1
那么我们就得到了一组新方程: x∗a+b∗p=1 若x 和 p不互质, 则 x和 p 存在公约数 d=gcd(x,p)>1
提取出d, 得到: d(x/d∗a+p/d∗b)=1 移项得到: (x/d∗a+p/d∗b)=1/d
易知 x , p 能整除 d, 所以括号内定为整数, 又因为d>1 ,等式右边必为真分数, 等式无解
证毕
(1).费马小定理(证明)
内容：费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。
inv[a]*a≡1(mod p) a^(p-1)≡1(mod p) a^(p-1)≡inv[a]*a(mod p) inv[a]=a^(p-2)modp
在是素数的情况下，对任意整数都有。
如果无法被整除，则有。
可以在为素数的情况下求出一个数的逆元，，即为逆元。
题目中的数据范围1<=x<=10^9，p=1000000007，p是素数；
所以x肯定就无法被p整除啊，所以最后就得出x^(p-2)为x的逆元啦
复杂度O(logn)；
x % p 中x的逆元为 quick_pow(x,p-2,p) x,y,mod （p是一个质数，而整数a不是p的倍数）
LL qkpow(LL a,LL p,LL mod) { LL t=1,tt=a%mod; while(p) { if(p&1)t=t*tt%mod; tt=tt*tt%mod; p>>=1; } return t; } LL getInv(LL a,LL mod) { return qkpow(a,mod-2,mod); }
(2)扩展欧几里得算法求逆元
扩展欧几里得算法可以参考小白书；
百度百科-乘法逆元中有这样一个例子:
求x，k就是扩展欧几里得算法了吧~
可扩展欧几里得求逆元a*inv[a]≡1(mod p)其中a，p互质；
所以可以转化为ax+bp=1，x=inv[a];
复杂度：O(logn)；
x % p 中x的逆元 先扩欧计算出x值，ex_gcd(a,p,inv_a,y)，逆元则为inv_a
LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 { if(b==0) { x=1,y=0; return a; } LL ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret; } LL getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1 { LL x,y; LL d=exgcd(a,mod,x,y); return d==1?(x%mod+mod)%mod:-1; }
(3) 求 1! ~ n! 的逆元
公式：inv[i]≡inv[i+1]?(i+1)(mod p)(inv[i]代表i！的逆元)
fac[i]∗inv[i]≡1(mod p)
fac[i+1]∗inv[i+1]≡1(mod p)=>fac[i]∗(i+1)∗inv[i+1]≡1(mod p)
由 同余的除法原理可得 : inv[i]≡inv[i+1]∗(i+1)
推导完毕
inline void get_finv(){ fac[1]=finv[0]=1; for(int i=2;i<=n;++i;++i) fac[i]=fac[i-1]*i%mod; finv[n]=quick_pow(fac[n],mod-2); for(int i=n-1;i;--i) finv[i]=finv[i+1]*(i+1)%mod; }
(4) 逆元线性筛 ( P为质数 )
求1,2,...,N关于P的逆元（P为质数）
公式：inv[i]≡inv[p%i]∗(−p/i)(mod p)
令 s=p/i,t=p%i, 则有：
s∗i+t=p (显然)
然后 s∗i+t≡0(mod p)
移项得 t≡−s∗i(mod p)
同除以 t∗i得t/(t∗i)≡−s∗i/(t∗i)(mod p)
将除法转化为乘法 => inv[i]≡−s∗inv[t](mod p)
于是将 s=p/i,t=p%i带入就可以得到: inv[i]≡inv[p%i]∗(−p/i)(mod p) 一个数的逆元等于它余数的逆元乘上积的相反数(此处要求是整数)
推导完毕
复杂度：O(N)
主要思想：将一个数的逆元与小于这个数的数的逆元表示，所以取余保证逆元数从小到大开始
LL inv[mod+5]; void getInv(LL mod) { inv[1]=1; for(int i=2;i<mod;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; }
相关文章：
https://blog.csdn.net/tobeyours/article/details/79619333
https://www.cnblogs.com/Judge/p/9383034.html
https://blog.csdn.net/qq_35416331/article/details/81059747
https://www.cnblogs.com/qdscwyy/p/7795368.html
