Super Pow：如何高效進行模冪運算

2020 年 3 月 12 日
筆記

來源：labuladong

作者：labuladong

今天來聊一道與數學運算有關的演算法題目，LeetCode 372 題 Super Pow，讓你進行巨大的冪運算，然後求餘數。

int superPow(int a, vector<int>& b);

要求你的演算法返回冪運算a^b的計算結果與 1337 取模（mod，也就是餘數）後的結果。就是你先得計算冪a^b，但是這個b會非常大，所以b是用數組的形式表示的。

這個演算法其實就是廣泛應用於離散數學的模冪演算法，至於為什麼要對 1337 求模我們不管，單就這道題可以有三個難點：

一是如何處理用數組表示的指數，現在b是一個數組，也就是說b可以非常大，沒辦法直接轉成整型，否則可能溢出。你怎麼把這個數組作為指數，進行運算呢？

二是如何得到求模之後的結果？按道理，起碼應該先把冪運算結果算出來，然後做% 1337這個運算。但問題是，指數運算你懂得，真實結果肯定會大得嚇人，也就是說，算出來真實結果也沒辦法表示，早都溢出報錯了。

三是如何高效進行冪運算，進行冪運算也是有演算法技巧的，如果你不了解這個演算法，後文會講解。

那麼對於這幾個問題，我們分開思考，逐個擊破。

如何處理數組指數

首先明確問題：現在b是一個數組，不能表示成整型，而且數組的特點是隨機訪問，刪除最後一個元素比較高效。

不考慮求模的要求，以b = [1,5,6,4]來舉例，結合指數運算的法則，我們可以發現這樣的一個規律：

看到這，我們的老讀者肯定已經敏感地意識到了，這就是遞歸的標誌呀！因為問題的規模縮小了：

    superPow(a, [1,5,6,4])  =>  superPow(a, [1,5,6])

那麼，發現了這個規律，我們可以先簡單翻譯出程式碼框架：

// 計算 a 的 k 次方的結果  // 後文我們會手動實現  int mypow(int a, int k);    int superPow(int a, vector<int>& b) {      // 遞歸的 base case      if (b.empty()) return 1;      // 取出最後一個數      int last = b.back();      b.pop_back();      // 將原問題化簡，縮小規模遞歸求解      int part1 = mypow(a, last);      int part2 = mypow(superPow(a, b), 10);      // 合併出結果      return part1 * part2;  }

到這裡，應該都不難理解吧！我們已經解決了b是一個數組的問題，現在來看看如何處理 mod，避免結果太大而導致的整型溢出。

如何處理 mod 運算

首先明確問題：由於電腦的編碼方式，形如(a * b) % base這樣的運算，乘法的結果可能導致溢出，我們希望找到一種技巧，能夠化簡這種表達式，避免溢出同時得到結果。

比如在二分查找中，我們求中點索引時用(l+r)/2轉化成l+(r-l)/2，避免溢出的同時得到正確的結果。

那麼，說一個關於模運算的技巧吧，畢竟模運算在演算法中比較常見：

(a*b)%k = (a%k)(b%k)%k

證明很簡單，假設：

a=Ak+B；b=Ck+D

其中 A,B,C,D 是任意常數，那麼：

ab = ACk^2+ADk+BCk+BD

ab%k = BD%k

又因為：

a%k = B；b%k = D

所以：

(a%k)(b%k)%k = BD%k

綜上，就可以得到我們化簡求模的等式了。

換句話說，對乘法的結果求模，等價於先對每個因子都求模，然後對因子相乘的結果再求模。

那麼擴展到這道題，求一個數的冪不就是對這個數連乘么？所以說只要簡單擴展剛才的思路，即可給冪運算求模：

int base = 1337;  // 計算 a 的 k 次方然後與 base 求模的結果  int mypow(int a, int k) {      // 對因子求模      a %= base;      int res = 1;      for (int _ = 0; _ < k; _++) {          // 這裡有乘法，是潛在的溢出點          res *= a;          // 對乘法結果求模          res %= base;      }      return res;  }    int superPow(int a, vector<int>& b) {      if (b.empty()) return 1;      int last = b.back();      b.pop_back();        int part1 = mypow(a, last);      int part2 = mypow(superPow(a, b), 10);      // 每次乘法都要求模      return (part1 * part2) % base;  }

你看，先對因子a求模，然後每次都對乘法結果res求模，這樣可以保證res *= a這句程式碼執行時兩個因子都是小於base的，也就一定不會造成溢出，同時結果也是正確的。

至此，這個問題就已經完全解決了，已經可以通過 LeetCode 的判題系統了。

但是有的讀者可能會問，這個求冪的演算法就這麼簡單嗎，直接一個 for 循環累乘就行了？複雜度會不會比較高，有沒有更高效的演算法呢？

有更高效的演算法的，但是單就這道題來說，已經足夠了。

因為你想想，調用mypow函數傳入的k最多有多大？k不過是b數組中的一個數，也就是在 0 到 9 之間，所以可以說這裡每次調用mypow的時間複雜度就是 O(1)。整個演算法的時間複雜度是 O(N)，N 為b的長度。

但是既然說到冪運算了，不妨順帶說一下如何高效計算冪運算吧。

如何高效求冪

快速求冪的演算法不止一個，就說一個我們應該掌握的基本思路吧。利用冪運算的性質，我們可以寫出這樣一個遞歸式：

這個思想肯定比直接用 for 循環求冪要高效，因為有機會直接把問題規模（b的大小）直接減小一半，該演算法的複雜度肯定是 log 級了。

那麼就可以修改之前的mypow函數，翻譯這個遞歸公式，再加上求模的運算：

int base = 1337;    int mypow(int a, int k) {      if (k == 0) return 1;      a %= base;        if (k % 2 == 1) {          // k 是奇數          return (a * mypow(a, k - 1)) % base;      } else {          // k 是偶數          int sub = mypow(a, k / 2);          return (sub * sub) % base;      }  }

這個遞歸解法很好理解對吧，如果改寫成迭代寫法，那就是大名鼎鼎的快速冪演算法。至於如何改成迭代，很巧妙，這裡推薦一位大佬的文章讓技術一瓜共食：快速冪演算法。

雖然對於題目，這個優化沒有啥特別明顯的效率提升，但是這個求冪演算法已經升級了，以後如果別人讓你寫冪演算法，起碼要寫出這個演算法。

至此，Super Pow 就算完全解決了，包括了遞歸思想以及處理模運算、冪運算的技巧，可以說這個題目還是挺有意思的，你有什麼有趣的題目，可以留言分享一下。