题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/super-pow/submissions/
题目描述
你的任务是计算 ab 对 1337 取模,a 是一个正整数,b 是一个非常大的正整数且会以数组形式给出。
示例 1:
输入:a = 2, b = [3]
输出:8
示例 2:
输入:a = 2, b = [1,0]
输出:1024
示例 3:
输入:a = 1, b = [4,3,3,8,5,2]
输出:1
示例 4:
输入:a = 2147483647, b = [2,0,0]
输出:1198
提示:
1 <= a <= 231 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0
解题思路
拿到题目先不急着写代码,首先来分析。
b是一个非常大的数字,大到必须要用vector来存储,ab肯定不是直接暴力求解可以求出的。
由数学知识可知,取模运算符合结合律,即(a * b)Mod c = ((a Mod c) * (b Mod c)) Mod c.在次方的运算过程中边取模边计算,数字会小得多。
那么,现在问题转换为如何将ab拆分,使得次方更好算。
我们这里先看指数部分,设
那么,可得
,我们可以得到了一个关于n的递推公式。
根据以上递推公式,就可以依次遍历数组b求解
源码展示
class Solution { public: int Loc_Pow(int a, int b) { int iBase = a, iRet = 1; while(b) { if(b % 2) iRet = ((long)iRet * iBase) % 1337; iBase = ((long)iBase * iBase) % 1337; b /= 2; } return iRet; } int superPow(int a, vector<int>& b) { int iRet = 1; for(auto iter : b) iRet = Loc_Pow(iRet, 10) * Loc_Pow(a, iter) % 1337; return iRet; } };
运行结果