【LeetCode每日一题】372. 超级次方【中等】

你的任务是计算 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

题解： 利用了乘方的乘法性质，如将2147483647的200次方分解成2147483647的20次方的10次方+2147483647的0次方。使用了递归和快速幂的思想。

class Solution {
public:
    int mod = 1337;
    int superPow(int a, vector<int>& b) {
        return dfs(a, b, b.size() - 1);
    }

    int dfs(int a, vector<int> b, int u){
        if(u == -1) return 1;
        //幂的分解
        return qpow(dfs(a, b, u - 1), 10) * qpow(a, b[u]) % mod;
    }

    int qpow(int a, int b){
        int ans = 1;
        a %= mod;
        while(b){
            if(b & 1) ans = ans * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return ans;
    }
};