所謂快速冪，顧名思義，快速冪就是快速算底數(shù)的n次冪。其時間復雜度為 O(log?N)， 與樸素的O(N)相比效率有了極大的提高。

熟悉<math.h>或<cmath>頭文件的人都會知道函數(shù)pow()的作用，沒錯就是計算一個數(shù)的幾次冪，其定義如下：

double pow(double x,double y);

它的功能就是計算x的y次冪，返回值就是所求結果。

舉個小例子:

以上就是pow()函數(shù)的用法了，當然數(shù)字可以換成變量。

對于小范圍的冪計算，我們可以直接調(diào)用pow()函數(shù)來解決，但當數(shù)據(jù)較大時，一是時間較慢，二是容易溢出。（冪運算還是很容易就溢出的，千萬不要小看冪運算的威力，可還記得這張圖嗎？）

2的200次冪，這個數(shù)小編已經(jīng)不會讀了，不知道你們怎么樣，這個數(shù)太大了，以至于C語言的任何基本數(shù)據(jù)類型都裝不下這個數(shù)，這里小編用到了python來計算2的200次冪。（一種支持高精度的語言）

因為冪運算的威力太大了，所以冪運算更多的考的是 a的b次冪取余m 的結果。（a^b%m）

重點來了?。。?/p>

快速冪算法用到了分治算法，冪運算的法則相信大家都知道，這里我們要用的只有一條，那就是同底數(shù)冪相乘，底數(shù)不變，指數(shù)相加?。?！

我們這里用的是它的逆過程，把一個大的指數(shù)拆成若干個較小的指數(shù)（兩個小的指數(shù)相加等于大的指數(shù)），然后把它們各自的結果相乘，最終的結果不變。怎么樣拆才能盡可能的提高速度呢？答案只有一個，每次拆的子部分盡量相等，這樣只需要進行一次計算就好了！

于是，

根據(jù)這三種情況我們來寫代碼就好了，這里同樣只寫下一個快速冪函數(shù)，和pow()一樣進行調(diào)用就好了！

這樣快速冪就寫好了。

大家還記得之前提到的 a^b%m 嗎？留作思考，開動腦筋想想應該怎么辦吧！