逆元

若$ax\equiv 1\pmod{m}$,则称x为a在模m意义下的逆元，记作$a^{-1}$
ps:
$\qquad$当(a,m)！=1时，不存在逆元

证明：
我们需要寻找一个整数M满足$M\equiv a^{-1} \pmod{m}$
当有$ax\equiv 1\pmod{m}$
此时有x满足$x\equiv \frac{1}{a}\pmod {m}$
所以x为a在mod m意义下的逆元

• 拓展欧几里得算法求逆元

• 线性递推求逆元

• 费马小定理求逆元

拓欧求逆元

根据线性同余方程可知
求解x相当于求解
$ax+my=1$的一组整数解
可知逆元的前提$(a,m)=1$,否则无解
拓展欧几里得可求其中的一组解
ps：
对于拓展欧拉求解的x,当a,m不互质时，也可以求解出一个数，但是这是$ax+my=gcd(a,m)$的一组解，其$x为a/gcd(a,m)$的逆元

线性递推求逆元

已知$1^{-1}\equiv 1\pmod{p}$
设$p=k\times i+r,r<i,1<i<p$
$k=p/i,r=p\%i$
将上式放到$\pmod{p}$的意义下会得到
$\qquad k\times i+r\equiv 0\qquad \qquad \pmod{p}$
同乘$i^{-1},r^{-1}$
$\qquad i^{-1}\equiv -k\times r^{-1}\qquad \qquad \pmod{p}$
$\qquad i^{-1}\equiv -p/i\times (p\%i)^{-1}\qquad \pmod{p}$
所以
$\qquad i^{-1}= -p/i\times (p\%i)^{-1}\mod{p}$
我们需要保证逆元为正整数，在右式中加上p,并不影响答案
$\qquad i^{-1}= p-p/i\times (p\%i)^{-1}\mod{p}$

	inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=p-p/i*inv[p%i]%p;
	}

ps:

在线性求解逆元中，p必须是质数

当两个数n,p不互质时并不存在逆元，而逆元n是从1~n的所有状态中转移过来的，所以p必须是质数

在线性求解逆元中，i必须小于p

当i>p时，对于公式
$\qquad i^{-1}= -p/i\times (p\%i)^{-1}\mod{p}$
需要求解的状态没有办法从已知状态求解
有如下定理
当$i>p$,$i$在$\mod{p}$意义下的逆元等价于$i\%p$,在$\mod {p}$意义下的逆元
即
$i^{-1}\equiv (i\%p)^{-1}\pmod {p}$
证明：
即在线性同余方程中
$i\times x+p\times y=1$，此时$i>p$
存在正整数q,使得
$(p\times q+p\%i)\times x+p\times y=1$
$(p\%i)\times x+p\times (y+q\times x)=1$
此时$x$是$p\%i$在$\mod p$意义下的逆元

费马小定理求逆元

$a\times a^{p-2}=a^{p-1}\equiv 1$
可知，a在mod p的意义下的逆元为$a^{p-2}$
用快速幂求解即可