快速冪取模算法
所謂的快速冪，實際上是快速冪取模的縮寫，簡單的說，就是快速的求一個冪式的模(余)。在程序設計過程中，經常要去求一些大數對于某個數的余數，為了得到更快、計算范圍更大的算法，產生了快速冪取模算法。我們先從簡單的例子入手：求$$a^{b}modc$$

算法1.直接設計這個算法：

int ans = 1; for(int i = 1;i<=b;i++) {ans = ans * a; } ans = ans % c;

缺點：這個算法存在著明顯的問題，如果a和b過大，很容易就會溢出。
于是我們進行改進：
算法2.改進算法：

int ans = 1; a = a % c; for(int i = 1;i<=b;i++) {ans = (ans * a) % c; } ans = ans % c;

這里補充一句，為什么每次循環取余一次和最后取余一次的結果相等呢？考慮這樣一個例子：5%3=2； 如果我們將5拆分成2和3，那么5加多少個3，除3取余后的結果都是一樣的。

這個算法在時間復雜度上沒有改進，仍為O(b)，不過已經好很多的，但是在c過大的條件下，還是很有可能超時，所以，我們推出以下的快速冪算法。

算法3.快速冪算法：

快速冪算法依賴于以下明顯的公式：

本算法的時間復雜度為O（logb），能在幾乎所有的程序設計（競賽）過程中通過，是目前最常用的算法之一。
代碼展示：

int PowerMod(int a, int b, int c) {int ans = 1;a = a % c;while(b>0) {if(b % 2 = = 1)ans = (ans * a) % c;b = b/2;a = (a * a) % c;}return ans; }

本算法的時間復雜度為O（logb），能在幾乎所有的程序設計（競賽）過程中通過，是目前最常用的算法之一。

傳送門——>矩陣快速冪(教主傳授)

---

如果這篇文章對你產生了幫助，就請給博主一個小小的贊吧！大家的點贊是我創作的最大動力！

總結

以上是生活随笔為你收集整理的通俗易懂，快速幂基本思想的全部內容，希望文章能夠幫你解決所遇到的問題。

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