LeetCode每日一题 372.超级次方

今天的LeetCode每日一题是LeetCode 372.超级次方，困难度为中等，先看题。

题目

你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

题解

好家伙今天的题目那是十分的短啊，很明显是一道数学题。要计算a的b次方，题目中说了b是一个非常大的数并且是以数组的形式给出，瞅瞅数组的长度。。。。

1 <= a <= 231 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

我超，心脏骤停，2000的长度，直接硬算那肯定是不行了， long long 也承接不了那么大的数。

我们先从取模运算下手，设mod为被取模的数，我们已知

ab % mod = (a % mod · b % mod) % mod

那么如果是以此公式用在幂运算上呢？

a² % mod = (a % mod · a % mod) % mod
a³ % mod = (a² % mod · a % mod) % mod
……
a¹⁰ % mod = (a⁹ % mod · a % mod) % mod

那么就非常明朗了，我们需要重新写一下pow()函数，来适配这个程序。

为了缩短时间复杂度，我们还要要解决幂运算，假如我们要计算a¹²³，我们可以知道

a¹²³=(a¹⁰⁰)¹ x (a¹⁰)² x (a¹)³

这样我们就可以直接按数位来取数组b里的数而不用将数组b想办法转为数字型变量了。

a^b=(a¹⁰⁰)^b[2] x (a¹⁰)^b[1] x (a¹)^b[0]

ok，问题解决，让我们开始写代码吧。

代码示例

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        int x=a;
        int ans=1;
        for(int i=b.size()-1;i>=0;i--)
        {
            ans=(ans*pow(x,b[i])%1337);
            x=pow(x,10);   //计算a^[10^(b.size()-i)]
        }
        return ans;
    }
    int pow(int a,int b)   //按照取模运算的乘法公式改写一下pow()函数
    {
        a=a%1337;
        int ans=1;
        for(int i=0;i<b;i++)
            if(a<4294967296)
                ans=(ans*a)%1337;
        return ans;
    }

};