高效進(jìn)行模冪運(yùn)算

文章目錄

• • 高效進(jìn)行模冪運(yùn)算
  • 一、題目描述
  • 二、分析
  • 三、代碼

一、題目描述

你的任務(wù)是計(jì)算 a^b 對 1337 取模，a 是一個(gè)正整數(shù)，b 是一個(gè)非常大的正整數(shù)且會以數(shù)組形式給出。

示例 1:

輸入: a = 2, b = [3] 輸出: 8

示例 2:

輸入: a = 2, b = [1,0] 輸出: 1024

二、分析

單就這道題可以有三個(gè)難點(diǎn)：

• 一是如何處理用數(shù)組表示的指數(shù)，現(xiàn)在 b 是一個(gè)數(shù)組，也就是說 b可以非常大，沒辦法直接轉(zhuǎn)成整型，否則可能溢出。你怎么把這個(gè)數(shù)組作為指數(shù)，進(jìn)行運(yùn)算呢？
• 二是如何得到求模之后的結(jié)果？按道理，起碼應(yīng)該先把冪運(yùn)算結(jié)果算出來，然后做 % 1337 這個(gè)運(yùn)算。但問題是，指數(shù)運(yùn)算你懂得，真實(shí)結(jié)果肯定會大得嚇人，也就是說，算出來真實(shí)結(jié)果也沒辦法表示，早都溢出報(bào)錯(cuò)了。
• 三是如何高效進(jìn)行冪運(yùn)算，進(jìn)行冪運(yùn)算也是有算法技巧的，如果你不了解這個(gè)算法，后文會講解。

那么對于這幾個(gè)問題，我們分開思考，逐個(gè)擊破。

如何處理數(shù)組指數(shù)：

• 首先明確問題：現(xiàn)在 b 是一個(gè)數(shù)組，不能表示成整型，而且數(shù)組的特點(diǎn)是隨機(jī)訪問，刪除最后一個(gè)元素比較高效。
• 不考慮求模的要求，以 b = [1,5,6,4] 來舉例，結(jié)合指數(shù)運(yùn)算的法則，我們可以發(fā)現(xiàn)這樣的一個(gè)規(guī)律：

看到這，我們的老讀者肯定已經(jīng)敏感地意識到了，這就是遞歸的標(biāo)志呀！因?yàn)閱栴}的規(guī)模縮小了：

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

那么，發(fā)現(xiàn)了這個(gè)規(guī)律，我們可以先簡單翻譯出代碼框架：

// 計(jì)算 a 的 k 次方的結(jié)果 // 后文我們會手動實(shí)現(xiàn) int mypow(int a, int k);int superPow(int a, vector<int>& b) {// 遞歸的 base caseif (b.empty()) return 1;// 取出最后一個(gè)數(shù)int last = b.back();b.pop_back();// 將原問題化簡，縮小規(guī)模遞歸求解int part1 = mypow(a, last);int part2 = mypow(superPow(a, b), 10);// 合并出結(jié)果return part1 * part2; }

到這里，應(yīng)該都不難理解吧！我們已經(jīng)解決了 b 是一個(gè)數(shù)組的問題，現(xiàn)在來看看如何處理 mod，避免結(jié)果太大而導(dǎo)致的整型溢出。

如何處理 mod 運(yùn)算：

• 首先明確問題：由于計(jì)算機(jī)的編碼方式，形如 (a * b) % base這樣的運(yùn)算，乘法的結(jié)果可能導(dǎo)致溢出，我們希望找到一種技巧，能夠化簡這種表達(dá)式，避免溢出同時(shí)得到結(jié)果。
• 比如在二分查找中，我們求中點(diǎn)索引時(shí)用 (l+r)/2 轉(zhuǎn)化成 l+(r-l)/2，避免溢出的同時(shí)得到正確的結(jié)果。
• 那么，說一個(gè)關(guān)于模運(yùn)算的技巧吧，畢竟模運(yùn)算在算法中比較常見：
  (a * b) % k = (a % k)(b % k) % k

證明很簡單，假設(shè)： a = Ak +B；b = Ck + D其中 A,B,C,D 是任意常數(shù)，那么： ab = ACk^2 + ADk + BCk +BDab % k = BD % k又因?yàn)?#xff1a; a % k = B；b % k = D所以： (a % k)(b % k) % k = BD % k 綜上，就可以得到我們化簡求模的等式了。

• 換句話說，對乘法的結(jié)果求模，等價(jià)于先對每個(gè)因子都求模，然后對因子相乘的結(jié)果再求模。
• 那么擴(kuò)展到這道題，求一個(gè)數(shù)的冪不就是對這個(gè)數(shù)連乘么？所以說只要簡單擴(kuò)展剛才的思路，即可給冪運(yùn)算求模：

三、代碼

int base = 1337;// 計(jì)算 a 的 k 次方然后與 base 求模的結(jié)果 int mypow(int a, int k) {// 對因子求模a %= base;int res = 1;for (int _ = 0; _ < k; _++) {// 這里有乘法，是潛在的溢出點(diǎn)res *= a;// 對乘法結(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; }

• 你看，先對因子 a 求模，然后每次都對乘法結(jié)果 res 求模，這樣可以保證 res *= a 這句代碼執(zhí)行時(shí)兩個(gè)因子都是小于base 的，也就一定不會造成溢出，同時(shí)結(jié)果也是正確的。
• 至此，這個(gè)問題就已經(jīng)完全解決了，已經(jīng)可以通過 LeetCode 的判題系統(tǒng)了。
  但是有的讀者可能會問，這個(gè)求冪的算法就這么簡單嗎，直接一個(gè) for 循環(huán)累乘就行了？復(fù)雜度會不會比較高，有沒有更高效地算法呢？
• 有更高效地算法的，但是單就這道題來說，已經(jīng)足夠了。
• 因?yàn)槟阆胂?#xff0c;調(diào)用 mypow 函數(shù)傳入的 k 最多有多大？k 不過是 b 數(shù)組中的一個(gè)數(shù)，也就是在 0 到 9 之間，所以可以說這里每次調(diào)用 mypow 的時(shí)間復(fù)雜度就是 O(1)。整個(gè)算法的時(shí)間復(fù)雜度是 O(N)，N 為 b 的長度。

如何高效求冪：
快速求冪的算法不止一個(gè)，就說一個(gè)我們應(yīng)該掌握的基本思路吧。利用冪運(yùn)算的性質(zhì)，我們可以寫出這樣一個(gè)遞歸式：

• 這個(gè)思想肯定比直接用 for 循環(huán)求冪要高效，因?yàn)橛袡C(jī)會直接把問題規(guī)模（b 的大小）直接減小一半，該算法的復(fù)雜度肯定是 log級了。
• 那么就可以修改之前的 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;} }

總結(jié)

以上是生活随笔為你收集整理的高效进行模幂运算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。