模意义下的乘法逆元

乘法逆元在我看来就相当于模意义下的除法，在模意义下，如果 $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。