#教學教學文(一-1) 程式設計上的模逆元 | 程式設計板

好的還是我！(廢話) 這篇要接續上一篇的內容繼續來說模逆元了！另外這篇文章還會用到之前說過的快速冪哦！那麼 Let’s go！為什麼數學上的模逆元和程式設計上的模逆元要分開討論呢？當然是因為我幹話太多把文章弄太長了啊(喂好啦認真上一篇文章的最後我們知道了可以用模逆元讓我們可以在mod某個數字的情況下做除法但是要怎麼找到這個模逆元呢？最暴力的方法反正mod n的情況下最多最多就是把1~n-1全部跑過一遍就可以知道模逆元存不存在了嘛！可是如果n=5的時候還好 n=10^9+7這種等級的話 O(n)暴力跑絕對不可行因此一個很神奇的數學定理出現啦它叫做「費馬小定理」簡單來說如果有一個「整數」a和一個「質數」p 那麼a^p = a (mod p) (呃呃中間的等於其實應該是三條線那個符號但是我不知道那個三條線的符號怎麼打@@ 如果看不慣這種寫法的話請上維基百科哦那上面有長的超好看的寫法) 這個定理又要怎麼幫助我們呢？這時候我們把它變個樣子： a^(p-2) * a^2 = a^(-1) * a^2 (mod p) 發現了嗎？「a^(p-2)」和a的模逆元「a^(-1)」在mod p的情況下是相等的！ (其實數學上不能說是「相等」而是說「同義」不過論結果是一樣的啦所以就不要虐待我了@@) 因此想要得到mod p時a的模逆元只要算a^(p-2)%p就可以了！「欸！阿求a^(p-2)還不是要跑p-2次才比暴力的p-1次少一次而已是有差哦？」是不是有人想說這句話啊？這時候就要搬出我們的快速冪啦！用快速冪的話 a^(p-2)在O(log(p-2))的時間內就能跑出來！是不是超級快的啊？ ……好吧應該沒有人會回答我它真的很快！比賽中常見的mod 10^9+7 或是我之前看過不知道從哪來的998244353 還有超級87的0x94878787(換成10進位是2491910023) 取log之後瞬間變成大約30！(log是以2為底) (註：上面三個都是質數哦) 接下來就是實做啦 Code： http://codepad.org/PCQc76xL 接下來應該很多人都有疑問「那如果要mod的數字不是質數要怎麼辦？」嘿好問題看著辦唄~(被打) 好啦其實啊在打比賽的時候通常是用不到的至少我不記得有遇到過因為一般的比賽都是mod質數不過不是mod質數的時候只要模反元素存在還是可以求的！這東西叫extgcd 中文是擴展歐幾里得算法它可以求ax+by=gcd(a, b)的解(a、b是已知數) 那麼為什麼extgcd對於求模反元素有用呢？首先我們從模反元素的定義出發改寫一下式子在mod n的時候 a * a^(-1) = 1 (mod n) 再來 a * a^(-1) + n*y = 1+0 = 1 (mod n) 有看到了嗎？已知a、n，求a^(-1)、y兩個未知數搭啦！可以用extgcd來算！不過很明顯的 gcd(a, n)必須是1 如果gcd(a, n)不是1的話那麼模反元素不存在！好啦接下來就是code時間 (呃呃因為我不知道extgcd的數學原理所以就先跳過了@@) Code： http://codepad.org/Ut2jyzQD 好了模逆元篇結束了！有問題都歡迎提出來討論然後如果我文章中有可以改進的地方也麻煩跟我說一下哦！下一篇：矩陣快速冪