讀完本文，你可以去力扣拿下如下題目：
-----------
今天來(lái)聊一道與數(shù)學(xué)運(yùn)算有關(guān)的題目末购，LeetCode 372 題 Super Pow，讓你進(jìn)行巨大的冪運(yùn)算藏否，然后求余數(shù)箫措。
int superPow(int a, vector<int>& b);
要求你的算法返回冪運(yùn)算 a^b 的計(jì)算結(jié)果與 1337 取模（mod，也就是余數(shù)）后的結(jié)果垫桂。就是你先得計(jì)算冪 a^b，但是這個(gè) b 會(huì)非常大专控，所以 b 是用數(shù)組的形式表示的抹凳。
這個(gè)算法其實(shí)就是廣泛應(yīng)用于離散數(shù)學(xué)的模冪算法，至于為什么要對(duì) 1337 求模我們不管伦腐，單就這道題可以有三個(gè)難點(diǎn)：
一是如何處理用數(shù)組表示的指數(shù)赢底，現(xiàn)在 b 是一個(gè)數(shù)組，也就是說(shuō) b 可以非常大柏蘑，沒辦法直接轉(zhuǎn)成整型幸冻，否則可能溢出。你怎么把這個(gè)數(shù)組作為指數(shù)咳焚，進(jìn)行運(yùn)算呢洽损？
二是如何得到求模之后的結(jié)果？按道理革半，起碼應(yīng)該先把冪運(yùn)算結(jié)果算出來(lái)碑定，然后做 % 1337 這個(gè)運(yùn)算。但問(wèn)題是又官，指數(shù)運(yùn)算你懂得延刘，真實(shí)結(jié)果肯定會(huì)大得嚇人，也就是說(shuō)六敬，算出來(lái)真實(shí)結(jié)果也沒辦法表示碘赖，早都溢出報(bào)錯(cuò)了。
三是如何高效進(jìn)行冪運(yùn)算外构，進(jìn)行冪運(yùn)算也是有算法技巧的普泡，如果你不了解這個(gè)算法，后文會(huì)講解典勇。
那么對(duì)于這幾個(gè)問(wèn)題，我們分開思考叮趴，逐個(gè)擊破割笙。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目眯亦，全部發(fā)布在 labuladong的算法小抄伤溉，持續(xù)更新。建議收藏妻率，按照我的文章順序刷題乱顾，掌握各種算法套路后投再入題海就如魚得水了。
如何處理數(shù)組指數(shù)
首先明確問(wèn)題：現(xiàn)在 b 是一個(gè)數(shù)組宫静，不能表示成整型走净，而且數(shù)組的特點(diǎn)是隨機(jī)訪問(wèn)券时，刪除最后一個(gè)元素比較高效。
不考慮求模的要求伏伯，以 b = [1,5,6,4] 來(lái)舉例橘洞，結(jié)合指數(shù)運(yùn)算的法則，我們可以發(fā)現(xiàn)這樣的一個(gè)規(guī)律：
看到這说搅，我們的老讀者肯定已經(jīng)敏感地意識(shí)到了炸枣，這就是遞歸的標(biāo)志呀！因?yàn)閱?wèn)題的規(guī)呐螅縮小了：
superPow(a, [1,5,6,4])
=> superPow(a, [1,5,6])
那么适肠，發(fā)現(xiàn)了這個(gè)規(guī)律，我們可以先簡(jiǎn)單翻譯出代碼框架：
// 計(jì)算 a 的 k 次方的結(jié)果
// 后文我們會(huì)手動(dòng)實(shí)現(xiàn)
int mypow(int a, int k);
int superPow(int a, vector<int>& b) {
// 遞歸的 base case
if (b.empty()) return 1;
// 取出最后一個(gè)數(shù)
int last = b.back();
b.pop_back();
// 將原問(wèn)題化簡(jiǎn)候引，縮小規(guī)模遞歸求解
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// 合并出結(jié)果
return part1 * part2;
}
到這里侯养，應(yīng)該都不難理解吧！我們已經(jīng)解決了 b 是一個(gè)數(shù)組的問(wèn)題背伴，現(xiàn)在來(lái)看看如何處理 mod沸毁，避免結(jié)果太大而導(dǎo)致的整型溢出。
如何處理 mod 運(yùn)算
首先明確問(wèn)題：由于計(jì)算機(jī)的編碼方式傻寂，形如 (a * b) % base 這樣的運(yùn)算息尺，乘法的結(jié)果可能導(dǎo)致溢出，我們希望找到一種技巧疾掰，能夠化簡(jiǎn)這種表達(dá)式搂誉，避免溢出同時(shí)得到結(jié)果。
比如在二分查找中静檬，我們求中點(diǎn)索引時(shí)用 (l+r)/2 轉(zhuǎn)化成 l+(r-l)/2炭懊，避免溢出的同時(shí)得到正確的結(jié)果。
那么拂檩，說(shuō)一個(gè)關(guān)于模運(yùn)算的技巧吧侮腹，畢竟模運(yùn)算在算法中比較常見：
(a * b) % k = (a % k)(b % k) % k
證明很簡(jiǎn)單，假設(shè)：
a = Ak +B稻励；b = Ck + D
其中 A,B,C,D 是任意常數(shù)父阻，那么：
ab = ACk^2 + ADk + BCk +BD
ab % k = BD % k
又因?yàn)椋?/p>
a % k = B；b % k = D
所以：
(a % k)(b % k) % k = BD % k
綜上望抽，就可以得到我們化簡(jiǎn)求模的等式了加矛。
換句話說(shuō)，對(duì)乘法的結(jié)果求模煤篙，等價(jià)于先對(duì)每個(gè)因子都求模斟览，然后對(duì)因子相乘的結(jié)果再求模。
那么擴(kuò)展到這道題辑奈，求一個(gè)數(shù)的冪不就是對(duì)這個(gè)數(shù)連乘么苛茂？所以說(shuō)只要簡(jiǎn)單擴(kuò)展剛才的思路已烤，即可給冪運(yùn)算求模：
int base = 1337;
// 計(jì)算 a 的 k 次方然后與 base 求模的結(jié)果
int mypow(int a, int k) {
// 對(duì)因子求模
a %= base;
int res = 1;
for (int _ = 0; _ < k; _++) {
// 這里有乘法，是潛在的溢出點(diǎn)
res *= a;
// 對(duì)乘法結(jié)果求模
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;
}
你看味悄，先對(duì)因子 a 求模草戈，然后每次都對(duì)乘法結(jié)果 res 求模，這樣可以保證 res *= a 這句代碼執(zhí)行時(shí)兩個(gè)因子都是小于 base 的侍瑟，也就一定不會(huì)造成溢出唐片，同時(shí)結(jié)果也是正確的。
至此涨颜，這個(gè)問(wèn)題就已經(jīng)完全解決了费韭，已經(jīng)可以通過(guò) LeetCode 的判題系統(tǒng)了。
但是有的讀者可能會(huì)問(wèn)庭瑰，這個(gè)求冪的算法就這么簡(jiǎn)單嗎星持，直接一個(gè) for 循環(huán)累乘就行了？復(fù)雜度會(huì)不會(huì)比較高弹灭，有沒有更高效地算法呢督暂？
有更高效地算法的，但是單就這道題來(lái)說(shuō)穷吮，已經(jīng)足夠了逻翁。
因?yàn)槟阆胂耄{(diào)用 mypow 函數(shù)傳入的 k 最多有多大捡鱼？k 不過(guò)是 b 數(shù)組中的一個(gè)數(shù)八回，也就是在 0 到 9 之間，所以可以說(shuō)這里每次調(diào)用 mypow 的時(shí)間復(fù)雜度就是 O(1)驾诈。整個(gè)算法的時(shí)間復(fù)雜度是 O(N)缠诅，N 為 b 的長(zhǎng)度。
但是既然說(shuō)到冪運(yùn)算了乍迄，不妨順帶說(shuō)一下如何高效計(jì)算冪運(yùn)算吧管引。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目闯两，全部發(fā)布在 labuladong的算法小抄褥伴，持續(xù)更新。建議收藏生蚁，按照我的文章順序刷題噩翠，掌握各種算法套路后投再入題海就如魚得水了戏自。
如何高效求冪
快速求冪的算法不止一個(gè)邦投，就說(shuō)一個(gè)我們應(yīng)該掌握的基本思路吧。利用冪運(yùn)算的性質(zhì)擅笔，我們可以寫出這樣一個(gè)遞歸式：
這個(gè)思想肯定比直接用 for 循環(huán)求冪要高效志衣，因?yàn)橛袡C(jī)會(huì)直接把問(wèn)題規(guī)模（b 的大型驮）直接減小一半，該算法的復(fù)雜度肯定是 log 級(jí)了念脯。
那么就可以修改之前的 mypow 函數(shù)狞洋，翻譯這個(gè)遞歸公式，再加上求模的運(yùn)算：
int base = 1337;
int mypow(int a, int k) {
if (k == 0) return 1;
a %= base;
if (k % 2 == 1) {
// k 是奇數(shù)
return (a * mypow(a, k - 1)) % base;
} else {
// k 是偶數(shù)
int sub = mypow(a, k / 2);
return (sub * sub) % base;
}
}
雖然對(duì)于題目绿店，這個(gè)優(yōu)化沒有啥特別明顯的效率提升吉懊，但是這個(gè)求冪算法已經(jīng)升級(jí)了，以后如果別人讓你寫冪算法假勿，起碼要寫出這個(gè)算法借嗽。
至此，Super Pow 就算完全解決了转培，包括了遞歸思想以及處理模運(yùn)算恶导、冪運(yùn)算的技巧，可以說(shuō)這個(gè)題目還是挺有意思的浸须，你有什么有趣的題目惨寿，不妨留言分享一下。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章删窒，手把手帶刷 200 道力扣題目裂垦，建議收藏！對(duì)應(yīng)的 GitHub 算法倉(cāng)庫(kù) 已經(jīng)獲得了 70k star易稠，歡迎標(biāo)星缸废！
