四種方法乘法逆元！四種！
寫在前面
刷題過程中，為了避免高精度的整數(shù)運(yùn)算，常常會(huì)要求答案對某個(gè)數(shù)取模。但這衍生了一個(gè)新問題，如果運(yùn)算過程中涉及了除法，如，如果先對a和b取模再做除法，會(huì)導(dǎo)致答案錯(cuò)誤。比如:
但是，
為了解決這個(gè)問題，我們需要學(xué)習(xí)新知識(shí)：模運(yùn)算下的乘法逆元。
下文中會(huì)用到一些歐幾里得算法的知識(shí)，忘了的老鐵可以點(diǎn)這里：淺談輾轉(zhuǎn)相除法
乘法逆元
什么是逆元呢？百度百科告訴我們：逆元是指一個(gè)可以「取消」另一給定元素運(yùn)算的元素。
比如，在實(shí)數(shù)的加法中，任意實(shí)數(shù) a 和它的相反數(shù) -a，互為加法逆元。因?yàn)閷τ谌我鈱?shí)數(shù) x，加上a之后，再加上-a，仍然等于 x，換言之，-a「取消」了x和a的加法運(yùn)算。
再比如，在實(shí)數(shù)的乘法中，任意不為0的實(shí)數(shù)b和它的倒數(shù)，互為乘法逆元。因?yàn)閷τ谌我鈱?shí)數(shù)x，乘上b之后，在乘上，仍然等于x，換言之，「取消」了x 和 b 的乘法運(yùn)算。
接下來看看模運(yùn)算下的乘法逆元定義：如果兩個(gè)整數(shù)a 和 b 滿足 ，即 ，則稱，a 和 b 互為模 p 的乘法逆元。
換言之，如果整數(shù)a, b, p 滿足，那么 b 可以「取消」 a 和任意整數(shù)x在模p時(shí)的乘法，即 a 和 b 互為模 p 的乘法逆元。即 ，證明過程如下：
舉個(gè)實(shí)際的例子：比如 10 和 12 互為模7時(shí)的乘法逆元。然后再找個(gè)整數(shù)，比如 18，此時(shí)有：
另有，
何時(shí)存在乘法逆元
結(jié)論
先說結(jié)論：「a 與 p 互質(zhì)」 是 「存在a關(guān)于模p的乘法逆元b」 的充分必要條件。
存在逆元 → 互質(zhì)
證明 「a 與 p 互質(zhì)」 是 「存在乘法逆元b」 的必要條件。不妨先假設(shè) a 與 b 互為模p時(shí)的乘法逆元，且a與p的最大公約數(shù)為d，則有：
顯然，a*b-1 為 p 的 n 倍，n 為整數(shù)，則上式轉(zhuǎn)化為：
將等式中的a與p用d代替，則等式轉(zhuǎn)化為：
顯然，x*b-n*y是一個(gè)整數(shù)，所以僅當(dāng)d為1時(shí)，即a與p互質(zhì)時(shí)，上述等式才可能成立。
互質(zhì) → 存在逆元
證明 「a 與 p 互質(zhì)」 是 「存在乘法逆元b」 的充分條件。
在證明之前先來回憶一下輾轉(zhuǎn)相除法：
不妨用r來表示模運(yùn)算的結(jié)果：
將上式用除法表示，則有：
由上述的m+2個(gè)等式移項(xiàng)可得：
將 rm-1，rm-2 ... 以及 r1 依次代入
可以得到用 a，p 以及 ni表示的等式：
其中，x 與 y 為 n1，n2，n3 ... 的加減乘的運(yùn)算結(jié)果，顯然為整數(shù)。
得證，當(dāng) a 與 p 互質(zhì)時(shí)，存在整數(shù)x與y 滿足
即，當(dāng) a 與 p 互質(zhì)時(shí)，存在整數(shù)x 與 a互為模p時(shí)的乘法逆元。
如何計(jì)算乘法逆元
擴(kuò)展歐幾里得算法
回憶一下歐幾里得的遞歸過程：
當(dāng) a 與 b 互質(zhì)時(shí)，有 x，y，x'，y' 滿足：
將上式合并移項(xiàng)：
令x，y，x'，y' 滿足下述關(guān)系，則對于任意 a 和 b 上述公式都能成立。
??好巧，這就是我們要尋找的x，y和x'，y'的計(jì)算公式。另外，當(dāng) b = 0，即到達(dá)歐幾里得算法的遞歸邊界時(shí)，令 x = 1, y = 0 即可滿足ax+by=1(此時(shí)的a顯然為1)。
于是我們得到了下述代碼，最終得到的 x 即為 a 在模 b 時(shí)的乘法逆元，當(dāng)然前提是函數(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;
}
費(fèi)馬小定理 & 快速冪
費(fèi)馬小定理：若 p 為素?cái)?shù)，且 gcd(a, p) = 1，則滿足
于是，a 在模 p 時(shí)的乘法逆元為，可用快速冪求得。
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 為素?cái)?shù)時(shí)有效，而擴(kuò)歐并沒有該限制。
線性求1到n中每個(gè)數(shù)的逆元
現(xiàn)在要求1到n中每個(gè)數(shù)i在模p時(shí)的乘法逆元。
特別的，i = 1時(shí)，其乘法逆元i-1為1。
當(dāng) i > 1 時(shí)，不妨先設(shè)：
則有：
而且，在遞推過程中，當(dāng)我們要求時(shí)，對于任意的都是已知的啦(因?yàn)?p mod i肯定小于 i)，所以可根據(jù) 通過常數(shù)次運(yùn)算得到。
inv[1]?=?1;
for?(int?i?=?2;?i?<=?n;?++i)?{
??inv[i]?=?(p-p/i)*inv[p%i]%p;
}
求任意n個(gè)整數(shù)的乘法逆元
設(shè)有 n 個(gè)整數(shù)，分別為 a1，a2，a3...，對應(yīng)的逆元為a1-1，a2-1，a3-1...。
設(shè)Si 為 a1 到 ai i 個(gè)數(shù)的乘積，Si-1 為 a1-1 到 ai-1 i 個(gè)數(shù)的乘積。那么 Si 與 Si-1 互為逆元。證明過程如下：
接下來，我們可以先求出 S1 到 Sn，然后通過擴(kuò)展歐幾里得或者快速冪求出 Sn 的乘法逆元 Sn-1。
又有
換言之，我們可以利用 ai可以取消ai-1乘法運(yùn)算的性質(zhì)，由Si-1 計(jì)算出 Si-1-1。
這樣就可以O(shè)(n)的計(jì)算出所有的 Si-1。
最后，由Si-1以及Si 計(jì)算出所有的 ai-1：
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;