寫在前面

刷題過程中，為了避免高精度的整數(shù)運算，常常會要求答案對某個數(shù)取模。但這衍生了一個新問題，如果運算過程中涉及了除法，如$\frac{a}{b}$，如果先對a和b取模再做除法，會導致答案錯誤。比如:
$$\frac{20}{5}mod10=4$$
但是，
$$\frac{20mod10}{5mod10}=0$$

為了解決這個問題，我們需要學習新知識：模運算下的乘法逆元。

乘法逆元

什么是逆元呢？百度百科告訴我們：逆元是指一個可以取消另一給定元素運算的元素。

比如，在實數(shù)的加法中，任意實數(shù) a 和它的相反數(shù) -a，互為加法逆元。因為對于任意實數(shù) x，加上a之后，再加上-a，仍然等于 x，換言之，-a取消了x和a的加法運算。

再比如，在實數(shù)的乘法中，任意不為0的實數(shù)b和它的倒數(shù)$\frac{1}{b}$，互為乘法逆元。因為對于任意實數(shù)x，乘上b之后，在乘上$\frac{1}{b}$，仍然等于x，換言之，$\frac{1}{b}$取消了x 和 b 的乘法運算。

接下來看看模運算下的乘法逆元定義：如果兩個整數(shù)a 和 b 滿足 $(a?b?1)modp=0$，即 $a?b\equiv 1(modp)$，則稱，a 和 b 互為模 p 的乘法逆元。

換言之，如果整數(shù)a, b, p 滿足$a?b\equiv 1(modp)$，那么 b 可以取消 a 和任意整數(shù)x在模p時的乘法，即 a 和 b 互為模 p 的乘法逆元。即 $x?a?b\equiv x(modp)$，證明過程如下：

$$\begin{array}{rl}xmodp& =x(a?b?1)+xmodp\\ & =(x?a?b?x)+xmodp\\ & =x?a?bmodp\end{array}$$

舉個實際的例子：比如 10 和 12 互為模7時的乘法逆元。然后再找個整數(shù)，比如 18，此時有：

$$18mod7=4$$

另有，

$$\begin{array}{rl}18?10?12mod7& =2160mod7\\ & =4\end{array}$$

何時存在乘法逆元

結(jié)論

先說結(jié)論：a 與 p 互質(zhì) 是 存在a關于模p的乘法逆元b 的充分必要條件。

存在逆元 → 互質(zhì)

證明 a 與 p 互質(zhì) 是 存在乘法逆元b 的必要條件。不妨先假設 a 與 b 互為模p時的乘法逆元，且a與p的最大公約數(shù)為d，則有：

$$(a?b?1)modp=0$$

顯然，a*b-1 為 p 的 n 倍，n 為整數(shù)，則上式轉(zhuǎn)化為：

$$(a?b?1)=np$$

將等式中的a與p用d代替，則等式轉(zhuǎn)化為：

$$\begin{array}{rl}(x?d?b?1)& =n?y?d\\ (x?d?b?n?y?d)& =1\\ (x?b?n?y)?d& =1\\ x?b?n?y& =\frac{1}{d}\end{array}$$

顯然，x*b-n*y是一個整數(shù)，所以僅當d為1時，即a與p互質(zhì)時，上述等式才可能成立。

互質(zhì) → 存在逆元

證明 a 與 p 互質(zhì) 是 存在乘法逆元b 的充分條件。

在證明之前先來回憶一下輾轉(zhuǎn)相除法：
$$\begin{array}{rl}gcd(a,p)& =gcd(p,amodp)\end{array}$$

不妨用r來表示模運算的結(jié)果：
$$\begin{array}{rl}gcd(a,p)& =gcd(p,r_1)\\ & =gcd(r_1,r_2)\\ & =...\\ & =gcd(r_{m?1},r_m)\\ & =1//因為a與p互質(zhì)\end{array}$$

將上式用除法表示，則有：
$$\begin{array}{rl}a& =n_{1}p+r_1\\ p& =n_2{r}_1+r_2\\ r_1& =n_3{r}_2+r_3\\ ...& =...\\ r_{m?3}& =n_{m?1}{r}_{m?2}+r_{m?1}\\ r_{m?2}& =n_m{r}_{m?1}\\ r_{m?1}& =1\\ r_m& =0\end{array}$$

由上述的m+2個等式移項可得：
$$\begin{array}{rl}{r}_1& =a?n_{1}p\\ r_2& =p?n_2{r}_1\\ ...& =...\\ r_i& =r_{i?2}?n_i?r_{i?1}\\ r_{m?1}& =r_{m?3}?n_{m?1}{r}_{m?2}\\ 特別的，1& =r_{m?1}\end{array}$$

將 r_m-1，r_m-2 … 以及 r₁ 依次代入
$$1=r_{m?1}$$

可以得到用 a，p 以及 n_i表示的等式：
$$ax+py=1$$

其中，x 與 y 為 n₁，n₂，n₃ … 的加減乘的運算結(jié)果，顯然為整數(shù)。

得證，當 a 與 p 互質(zhì)時，存在整數(shù)x與y 滿足
$$\begin{array}{rl}ax+py& =1\\ ax?1& =py\\ (ax?1)modp& =0\\ ax& \equiv 1(modp)\end{array}$$

即，當 a 與 p 互質(zhì)時，存在整數(shù)x 與 a互為模p時的乘法逆元。

如何計算乘法逆元

擴展歐幾里得算法

回憶一下歐幾里得的遞歸過程：
$$\begin{array}{rl}gcd(a,b)& =gcd(b,amodb)\\ & =gcd(b,a?b?\frac{a}{b}?)\end{array}$$

當 a 與 b 互質(zhì)時，有 x，y，x'，y' 滿足：
$$?\begin{array}{r}ax+by=1\\ b{x}^{\prime }+(a?b?\frac{a}{b}?)y^{\prime }=1\end{array}$$

將上式合并移項：
$$\begin{array}{rl}b{x}^{\prime }+(a?b?\frac{a}{b}?)y^{\prime }& =ax+by\\ a(x?y^{\prime })+b(y?(x^{\prime }??\frac{a}{b}?)y^{\prime })& =0\end{array}$$

令x，y，x'，y' 滿足下述關系，則對于任意 a 和 b 上述公式都能成立。
$$?\begin{array}{rl}x& =y^{\prime }\\ y& =(x^{\prime }??\frac{a}{b}?)y^{\prime }\end{array}$$

😯好巧，這就是我們要尋找的x，y和x'，y'的計算公式。另外，當 b = 0，即到達歐幾里得算法的遞歸邊界時，令 x = 1, y = 0 即可滿足ax+by=1(此時的a顯然為1)。

于是我們得到了下述代碼，最終得到的 x 即為 a 在模 b 時的乘法逆元，當然前提是函數(shù)的返回值為1，即 a 與 b 互質(zhì)。

int exgcd(int a,int b,int &x,int &y) {if(b==0) {x=1;y=0;return a;}int r = exgcd(b,a%b,x,y);int t = y;y = x-(a/b)*y;x = t;return r; }

費馬小定理 & 快速冪

費馬小定理：若 p 為素數(shù)，且 gcd(a, p) = 1，則滿足
$$\begin{array}{r}{a}^{p?1}\equiv 1(modp)\\ a?a^{p?2}\equiv 1(modp)\end{array}$$

于是，a 在模 p 時的乘法逆元為$a^{p?2}$，可用快速冪求得。

inline int quick_power(int a, int b, int p) {int ans = 1;a = (a % p + p) % p;for (; b; b >>= 1) {if (b & 1) ans = (a * ans) % p;a = (a * a) % p;}return ans; } // quick_power(a, p-2, p) 即為 a 的乘法逆元。

值得注意的是，該算法僅在 p 為素數(shù)時有效，而擴歐并沒有該限制。

線性求1到n中每個數(shù)的逆元

現(xiàn)在要求1到n中每個數(shù)i在模p時的乘法逆元。

特別的，i = 1時，其乘法逆元i^-1為1。

當 i > 1 時，不妨先設：
$$?\begin{array}{rl}k& =?\frac{p}{i}?\\ j& =pmodi\end{array}$$
則有：
$$?\begin{array}{rl}p& \equiv 0(modp)\\ (k?i+j)& \equiv 0(modp)\\ (k?i+j)?i^{?1}?j^{?1}& \equiv 0(modp)\\ k?j^{?1}+i^{?1}& \equiv 0(modp)\\ ?k?j^{?1}& \equiv i^{?1}(modp)\\ ??\frac{p}{i}??(pmodi{)}^{?1}& \equiv i^{?1}(modp)\end{array}$$

而且，在遞推過程中，當我們要求$i^{?1}$時，對于任意的$(pmodi{)}^{?1}$都是已知的啦(因為 p mod i肯定小于 i)，所以可根據(jù)$(pmodi{)}^{?1}$ 通過常數(shù)次運算得到$i^{?1}$。
$$i^{?1}\equiv ?\begin{array}{rl}1& ,i=1\\ ??\frac{p}{i}?(pmodi{)}^{?1}& ,i>2\end{array}(modp)$$

inv[1] = 1; for (int i = 2; i <= n; ++i) {inv[i] = (p-p/i)*inv[p%i]%p; }

求任意n個整數(shù)的乘法逆元

設有 n 個整數(shù)，分別為 a₁，a₂，a₃…，對應的逆元為a₁^-1，a₂^-1，a₃^-1…。

設S_i 為 a₁ 到 a_i i 個數(shù)的乘積，S_i^-1 為 a₁^-1 到 a_i^-1 i 個數(shù)的乘積。那么 S_i 與 S_i^-1 互為逆元。證明過程如下：

$$\begin{array}{rl}\prod _{i=1}^n{a}_i?{a_i}^{?1}& \equiv 1modp\\ \prod _{i=1}^n{a}_i?\prod _{i=1}^n{a_i}^{?1}& \equiv 1modp\\ S_n?{S_n}^{?1}& \equiv 1modp\end{array}$$

接下來，我們可以先求出 S₁ 到 S_n，然后通過擴展歐幾里得或者快速冪求出 S_n 的乘法逆元 S_n^-1。

又有
$$\begin{array}{rl}{S_i}^{?1}?{a_{i+1}}^{?1}?a_{i+1}& \equiv {S_i}^{?1}(modp)\\ {S_{i+1}}^{?1}?a_{i+1}& \equiv {S_i}^{?1}(modp)\end{array}$$

換言之，我們可以利用 a_i可以取消a_i^-1乘法運算的性質(zhì)，由S_i^-1 計算出 S_i-1^-1。

這樣就可以O(n)的計算出所有的 S_i^-1。

最后，由S_i^-1以及S_i 計算出所有的 a_i^-1：
$${a_i}^{?1}\equiv S_{i?1}?{S_i}^{?1}(modp)$$

s[0] = 1; for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p; sv[n] = quick_power(s[n], p - 2); for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p; for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

總結(jié)

以上是生活随笔為你收集整理的乘法逆元的解法及证明的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。