(數學渣，下面的文字可能有誤，歡迎指教)

乘法逆元的定義貌似是基于群給出的，比較簡單地理解，可以說是倒數的概念的推廣。記a的關于模p的逆元為a^-1,則a^-1滿足aa^-1≡ 1(mod p)

加減乘與模運算的順序交換不會影響結果，但是除法不行。有的題目要求結果mod一個大質數，如果原本的結果中有除法，比如除以a,那就可以乘以a的逆元替代。

在mod p的運算中，a存在乘法逆元當且僅當a與p互質。一般題目給的是一個大質數，所以只要a不是p的倍數，就以求乘法逆元。

目前了解到的求法有三種：

1.擴展歐幾里得。aa^-1≡ 1(mod p)，可以轉換為aa^-1 + py = 1，即是擴展歐幾里得所能解的ax + by = gcd(a, b)。最常用的解法。

intx, y;int extgcd(int a, int b, int &x, int &y)

{if (b == 0){

x= 1;

y= 0;returna;

}int gcd = exgcd(b, a %b, x, y);int tmp =x;

x=y;

y= tmp - (a/b) *y;returngcd;

}/*求解ax+by=gcd(a,b)，亦即ax≡1(mod b)。函數返回值是a,b的最大公約數，而x即a的逆元。

注意a, b不能寫反了。*/

2.由費馬小定理a^(p-1)≡ 1(mod p)(p為素數)，稍作變形即是 aa^(p-2)≡ 1(mod p)，是不是發現了，a^(p-2)即是a的逆元，這個可以用快速冪來求。

3.網上看到的一個很厲害的o(n)的遞推，求前n個逆元，不知道是怎么推出來的，但是可以簡單地證明一下正確性(要求所mod p為素數)。

首先，1的逆元是1，沒什么疑問。

假設前i個數的逆元已經求出，那么

i^-1 = (p%i)^-1 * (p - [p/i]) % p。其中[]表示去尾取整。

(p%i)^-1其實就是(p-[p/i]i)^-1，然后我們左右乘以i，

ii^-1 = (p-[p/i]i)^-1 * ((i-1)p + p-[p/i]i) % p，

其實就是ii^-1 = k^-1 * ((i-1)p + k) % p = 0 + 1 = 1，這樣就證完了＝。＝

//字體真糟糕。。

int[] inv = new int[MAXN];

inv[1] = 1;for (int i = 2; i

inv[i]= inv[MOD%i]*(MOD-MOD/i)%MOD;

總結

以上是生活随笔為你收集整理的java求乘法逆元的代码_求乘法逆元的几种方法的全部內容，希望文章能夠幫你解決所遇到的問題。

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