乘法逆元

· · 算法·理论

现有一个线性同余方程ax≡1(\bmod \ p)， 则称x为a在模p意义下的逆元。 那么如何求逆元呢？ 我们先求简单一点的情况， 求单个数的逆元。\ 此方程ax≡1(\bmod \ p)等价于求满足ax+py=1， 的解。 显然，

接下来介绍扩展欧几里得算法来求逆元。 ## **扩欧** $$ax≡1(\bmod \ p),(a,p)=1$$ 此方程化为 $$ax+py=1,(a,p)=1$$ 将1变换一下可以得到 $$ax+py=(a,p)=(p,a\bmod p)=px_0+(a\bmod p)y_0$$ 注意到 $$a\bmod p=a-\lfloor\frac{a}{p} \rfloor \times p$$ 因此原式又可以化为 $$px_0+(a-\lfloor\frac{a}{p} \rfloor \times p)y_0=1$$ 去括号展开一下 $$px_0+ay_0-\lfloor\frac{a}{p} \rfloor \times p y_0=1$$ $$p(x_0-\lfloor\frac{a}{p} \rfloor \times y_0)+ay_0=1$$ 观察一下两个方程的系数 $$ax+py=1$$ $$p(x_0-\lfloor\frac{a}{p} \rfloor \times y_0)+ay_0=1$$ 便可以得到一个惊人的结论， 我们在求解方程$ay_0+px_0=1$的时候， 得到的$x_0,y_0$可以推出方程$ax+py=1$的$x,y$， 也就是说， 我们可以通过计算$x_0,y_0$来得到$x,y$。 然后有注意到， 我们这样子计算下去， 类似于欧几里得求最大公约数的过程， 最终我们会使得$p$变成0， 此时的方程为 $$1\times x+0\times y=1$$ 可以得到$x=1,y=0$的一组解， 然后可以一直往上求解出$x,y$的值。 由于欧几里得算法求最大公约数的时间复杂度为$O(\log n)$， 所以扩展欧几里得算法的时间复杂度也是$O(\log n)$。 这样我们便求解出了单个数的逆元。 ## **费马小定理** 费马小定理描述如下 $$a^{p-1}≡1(\bmod \ p),p∈Prime,(a,p)=1$$ 证明读者自行查阅资料。 有了这个定理， 求解逆元便很简单了。 将费马小定理的式子变一下形可以得到 $$a\times a^{p-2}≡1(\bmod \ p )$$ 观察可知$a^{p-2}$就是$a$在模$p$意义下的逆元， 求解方法考虑使用快速幂。 时间复杂度$O(\log p)$。 ## **欧拉定理** 欧拉定理描述如下， 首先定义， $$φ(n)$$ 表示$[1,n]$以内与$n$互素的数的个数， 那么欧拉定理， $$a^{φ(p)}≡1(\bmod \ p )$$ 两边同时乘以$a^{-1}$可以得到， $$a^{φ(p)-1}≡a^{-1}(\bmod \ p )$$ 那么我们就找到了求解逆元的另一种方式， 时间复杂度根据欧拉函数的求解方式计算， 时间复杂度在$O(\sqrt p)\sim O(\log p)$不等。 当然，这个不用考虑$p$是不是素数的情况。 ## **线性求逆元** 刚才讨论到的都只能求单个的逆元， 可是求多个的逆元时时间复杂度又很高， 这时候我们可以使用线性求逆元。 线性求逆元可以解决求$1\sim n$的逆元。 我们要求解 $$i^{-1}≡1(\bmod \ p)$$ 首先 $$1^{-1}≡1(\bmod \ p)$$ 这是很显然的。 我们将原式变一下形， $$p=\lfloor \frac{p}{i} \rfloor \times i + p\bmod i$$ $$∵p≡0(\bmod \ p )$$ $$∴\lfloor \frac{p}{i} \rfloor \times i + p\bmod i≡0(\bmod \ p )$$ 两边同时乘上$i^{-1}\times (p\bmod i)^{-1}$可以得到 $$\lfloor \frac{p}{i} \rfloor \times (p\bmod i)^{-1}+i^{-1}≡0(\bmod \ p )$$ $$∴i^{-1}≡-\lfloor \frac{p}{i} \rfloor \times (p\bmod i)^{-1}(\bmod \ p )$$ 由于$p \bmod i <i$， 所以我们求解$i$的逆元时， 可以利用前面求解过的逆元来求解$i^{-1}$， 这样我们就做到了线性求解逆元， 时间复杂度$O(n)$。 ## **阶乘求逆元** 我们求出 $$(∏_{i=1}^{n}i)^{-1}$$ 也就是 $$n!^{-1}$$ 记为 $$f_n$$ 那么 $$f_i=f_{i+1}\times (i+1)$$ 在记 $$inv_i$$ 表示$i$的逆元， 那么， $$inv_i=f_i\times (i-1)!$$ 这里$0!=1

这样我们就完成了O(n+\log p)接近线性求逆元了。

前缀积求逆元

上面的线性求逆元只能求出1\sim n的逆元，而前缀积求逆元可以求出任意n个数的逆元。具体如下，现在要求求出a_i,(1≤i≤n)的逆元。 令

f(k)=∏_{i=1}^{k}a_i

求出

f(n)^{-1}

定义

inv_i

表示a_i的逆元 那么

inv_i=f(i+1)^{-1}\times f(i)

因此我们可以先处理出f(n)^{-1}， 然后， 根据上面的递推公式可以得到inv_i。这样的时间复杂度为O(n+\log \ p )。适用性很强。

线性筛

还是求解[1,n]的逆元。 我们现将所有Prime∈[1,n]用线性筛求解出来， 然后对于每一个数i∈[1,n]，

i^{-1}=mpf(i)^{-1}\times (\frac{i}{mpf(i)})^{-1} 我们现将所有的素数的逆元求解出来， 然后将每一个数的逆元通过前面计算过的计算出来， 因为$\frac{i}{mpf(i)}$是肯定是前面已经计算过的， 这里的时间复杂度大约为 $$O(n+\frac{n\log p}{㏑_n})$$ 。