LeetCode-372 超级次方

题目来源:力扣(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拆分,使得次方更好算。

由题目得 LeetCode-372 超级次方 ,其中 m 为 b数组的长度。

我们这里先看指数部分,设 LeetCode-372 超级次方 那么,可得LeetCode-372 超级次方,我们可以得到了一个关于n的递推公式。

带入原式,就可以得到关于a的递推公式:LeetCode-372 超级次方

根据以上递推公式,就可以依次遍历数组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;
    }
};

运行结果

LeetCode-372 超级次方

 

上一篇:PTA练习7-9 计算天数 (15 分)


下一篇:python练习2