浅谈乘法逆元
乘法逆元，一般用于求解(frac{A}{C}(mod ~ P))的值，因为我们通过模的定义可以知道上式显然不等于(frac{A \% P}{B \% P})。例子有很多不再举了。那么如果我们要求上式大多数情况都需要借助逆元。
首先是定义：
若(A imes X equiv 1 (mod ~ P))，并且(A perp P)((perp)：互质)，那么我们就称(X)为(A)的逆元，简称为(A^{- 1})，也就是(A)在(mod ~ P)意义下的倒数。
借此我们可以知道(frac{A}{C}(mod ~ P))的求法：我们先求出(C)在(mod ~ P)意义下的逆元，然后(imes A)就是答案了。那么我们主要求的就是(C)的逆元。
扩展欧几里得版
首先从最简单开始，就是一个扩展欧几里得，直接求解(A imes X + P imes Y = 1)就行了。
inline void Exgcd(int A, int P, int X, int Y) {
if (! B) X = 1, Y = 0 ;
else Exgcd(P, A % P, Y, X), Y -= A / B * X ;
}
这个方法虽然时间上比较慢，但是有一个优点，就是当(A)与(P)不互质的时候，依然可以适用。但是下面介绍的其他方法就必须满足(A perp P)了。
费马小定理版
回顾一下费马小定理的内容：
若(A perp P)， 则(A^{P – 1} equiv 1(mod ~ P))。
我们可以把它运用到乘法逆元里。结合(A imes X equiv 1(mod ~ P))可以得到(A imes X equiv A^{P – 1}(mod ~ P))。当(P)为质数的时候，我们把左右都除以一个(A)可以得到(X equiv A^{P – 2}(mod P))。然后就可以一个快速幂求出来了。
inline void Fpm(int A, int P) {
int Ans = 1 ; int M = P ;
A %= M ; P -= 2 ;
while (P) {
if (P & 1) Ans = Ans * A % M ;
A = A * A % M ; P >> = 1 ;
} return Ans % M ;
}
上面的复杂度是(O(logN))的，在求多个逆元的时候可能(O(NlogN))是过不去的。当然我们还有一种利用地推打出逆元表的方法做到(O(N)).
欧拉筛版
设(INV[i])为(i)的逆元。我们知道有(INV[A] = A ^ {P – 2}(mod ~ P),~INV[B] = B ^ {P – 2} (mod ~ P))
我们利用费马小定理可以得(INV[A imes B] = (AB) ^ {P – 2} (mod P))也就是说(INV[A imes B] = INV[A] imes INV[B])。求得递推式。我们就可以利用欧拉筛。
递推版
为了方便起见就直接写过程了。
设(P = kA + r~~(r in [0, P)~))。因为我们知道任何一个数都可以写成这个形式嘛。
那么有(kA + r equiv 0 (mod ~ P))
因为(A^{P – 1} equiv 1(mod ~ P))
所以((kA +r) imes A^{- 1} imes r^{- 1} equiv 0 (mod ~ P))
把左边的括号拆开得(kr^{- 1} + A^{- 1} equiv 0 (mod ~ P))
移项：(A^{- 1} equiv -kr^{- 1})
在这里我们知道(k = lfloor frac{P}{A} floor)。
(A^{- 1} equiv -lfloor frac{P}{A} floor imes r^{- 1})
并且我们还知道(r ≤ A)。那么我们就可以借用数组(INV[r])完成递推。同时我们还知道(r = P \% A)
最后得到(INV[A] = (P – lfloor frac{P}{A} floor) imes INV[P\% A])
递推完成，时间复杂度(O(N))。
for (int i = 2 ; i <= N ; i ++)
INV[i] = P – (P / i) * INV[P % i] % P;
当然不要忘了初始化的问题。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/214841.html原文链接：https://javaforall.net
