點擊上方藍字設為星標
今天來聊一道與數學運算有關的算法題目，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 就算完全解決了，包括了遞歸思想以及處理模運算、冪運算的技巧，可以說這個題目還是挺有意思的，你有什麼有趣的題目，可以留言分享一下。
歷史文章：
回溯算法團滅排列/組合/子集問題
加密算法的前世今生
這個問題不簡單：尋找缺失元素