若线性同余方程 \(ax\equiv1(\mod b)\)，则称 \(x\) 为 \(a\mod b\)时的逆元，记作\(a^{-1}\)。
扩展欧几里得求逆元。
要求 \(gcd(a,b)=1\).
int exgcd(int a,int b,int&x,int&y){
if(!b)return x=1,y=0,a;
int g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
\((x\mod p+p)\mod p\) 即为 \(a\mod b\) 逆元。
费马小定理求逆元。
要求 \(b\) 为质数。
\(ax\equiv a^{b-1}(\mod b)\)，则 \(x\equiv a^{b-2}(\mod b)\).
inline int po(int x,int k,int mod,int re=1){for(;k;k>>=1,x=x*x%mod)(k&1)&&(re=re*x%mod);return re;}
\(po(a,b-2,b)\) 即为 \(a\mod b\) 的逆元。
线性求逆元。
求 \(1\) 到 \(n\) d的逆元。
\(1\) 的逆元为 \(1\).
设 \(k=\left \lfloor p/i \right \rfloor,j=p\mod i\)，则 \(p=k*i+j\)，\(k*i+j \equiv 0(\mod p)\).
两边同乘 \(i^{-1}+j^{-1}\)，得到 \(k*j^{-1}+i^{-1} \equiv 0(\mod p)\).
于是有 \(i^{-1} \equiv -\left \lfloor p/i \right \rfloor * (p\mod i)^{-1}\)，将负数加上模数即可。
inline void prework(int n){
inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}