逆元
violetctl39
·
·
个人记录
逆元！
\large by\ ctldragon
关于逆元的4种求法总结。
扩欧求解
运用扩展欧几里得求解逆元。
```cpp
int exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1,y=0;return a;}
int res=exgcd(b,a%b,x,y);
int tmp=x;
x=y;y=tmp-a/b*y;
return res;
}
int exgcd_inv(int a,int mod)
{
int d,x,y;
d=exgcd(a,mod,x,y);
return d==1?(x+mod)%mod:-1;
}
```
## 费马小定理求解
利用快速幂和费马小定理。
当 $p$ 为质数时，有 $a^{p-1}\equiv 1\ (mod\ p)$ 。
可得： $a·a^{p-2}\equiv 1\ (mod\ p)$ ，$a^{p-2}$ 就是 $a$ 的逆元。
```cpp
int ksm(int x,int y,int mod)
{
int res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod,y>>=1;
}
return res;
}
int fermat_inv(int x,int mod){return ksm(x,mod-2,mod);}
```
## 线性求逆元
证明：
首先，$1^{-1}\equiv 1\ (mod\ p)
设 p=k*i+r,r<i ，可得 k\times i+r\equiv 0\ (mod\ p) 。
两边同乘 i^{-1},r^{-1} 得 k\times r^{-1}+i^{-1}\equiv 0\ (mod\ p)
移项得 i^{-1}\equiv -k\times r^{-1} ，消元得 i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor\times (p\ mod\ i)\ (mod\ p)
因为此时求的逆元为负数，我们需要将它变正，可以加上一个 p\times r^{-1} 。
最后得 i^{-1}\equiv (p-\lfloor \frac{p}{i}\rfloor)\times (p\ mod\ i)\ (mod\ p)
inv[1]=1;
for(int i=1;i<mod;++i)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
递归求逆元
我们可以从线性求逆元发现， i 的逆元只与 p\ mod\ i 有关，所以我们可以递归求解逆元，时间复杂度和费马小定理求解都是 O(logn) 的时间复杂度。
为了防止爆 long\ long ，我们可以用 __int128 进行乘法取模来保证正确性。
int gsc(int x,int y){return (__int128)x*y%p;}
int inv(int x){return x==1?1:gsc(p-p/x,inv(p%x));}
这种求逆元方法代码极短！很方便！
总结
扩展欧几里得求解是最快的，常数小，但比较难写。
费马小定理求解从各各方面来看都没有递归求解好，所以很不理解很多人推崇它的理由。
线性求逆元是 O(n) 时间复杂度，在大量用到逆元时适合用线性来预处理逆元。