乘法逆元在我看来就相当于模意义下的除法，在模意义下，如果 a 和 m 互质，那么 a 关于模 m 的乘法逆元 a^{-1} 存在，且满足 a \times a^{-1} \equiv 1 \pmod m。
本文主要讲解乘法逆元的四种求法。
费马小定理方法
费马小定理表明对于任意整数 a 和素数 p，有 a^{p-1} \equiv 1 \pmod p。由此我们可以推出 a \times a^{p-2} \equiv 1 \pmod p，所以 a^{p-2} 就是 a 关于模 p 的乘法逆元。接下来我们就可以通过快速幂的方法求出 a^{p-2}。但要注意的是，这个方法只适用于模数是素数的情况。
LLI qpow(LLI a,LLI b,LLI p){
LLI ans=1;
while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
扩展欧几里得方法
我们知道a在模m意义下的乘法逆元是指一个整数x，使得ax \equiv 1 \pmod m。这个式子也可以改写成ax+my=1，这是就可以通过扩展欧几里得算法求出x的值。
#define T3I tuple<int,int,int>
T3I exgcd(int a,int b){
int x1=1,x2=0,x3=0,x4=1,c;
while(b){
c=a/b;
tie(x1,x2,x3,x4,a,b)=make_tuple(x3,x4,x1-x3*c,x2-x4*c,b,a-b*c);
}
return make_tuple(x1,x2,a);
}
int inv(int a,int m){
auto [x,y,d]=exgcd(a,m);
return d==1?(x+m)%m:-1;
}
顺便提一下，如果不是求逆元而是求ax\equiv b \pmod m，可以通过扩展欧几里得算法直接求出x的值，也可以先求a的逆元，将逆元乘以b得到解。
线性递归方法
如果要求出1...n每个数在模m意义下的乘法逆元，可以通过线性递推的方法求出。
首先可以知道1的乘法逆元必然是1,接下来考虑a的乘法逆元,我们知道：
\lfloor \frac{m}{a} \rfloor a + m \bmod a = m
因此
\lfloor \frac{m}{a} \rfloor a + m \bmod a \equiv 0 \pmod m
两边同时乘以a^{-1}，得到：
\lfloor \frac{m}{a} \rfloor + a^{-1} (m \bmod a) \equiv 0 \pmod m
再同时乘以m\bmod a的乘法逆元，得到：
\begin{align}
\lfloor \frac{m}{a} \rfloor (m \bmod a)^{-1} + a^{-1} &\equiv 0 \pmod m\\
a^{-1} &\equiv -\lfloor \frac{m}{a} \rfloor (m \bmod a)^{-1} \pmod m
\end{align}
而m\bmod a显然是小于a的，所以我们可以通过递归的形式和迭代的方式求出a的乘法逆元。
int inv[N];
void init(int n,int p){
inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=(p-p/i)*inv[p%i]%p;
}
似乎还有一种方法可以线性求任n个数的逆元，见OI-wiki。