淺談乘法逆元

乘法逆元，一般用于求解(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;

當然不要忘了初始化的問題。

總結

以上是生活随笔為你收集整理的乘法逆元 java_浅谈乘法逆元(示例代码)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。