超级次方

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-pow

题目描述:

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

思路:

利用公式：(a∗b)%mod=((a%mod)∗(b%mod))%mod

代码实现：

class Solution {
    public int mod = 1337;
    public int superPow(int a, int[] b) {
        return dfs(a, b, b.length - 1);
    }
    public int dfs(int a, int[] b, int u) {
        if (u == -1) return 1;
        return qpow(dfs(a, b, u - 1), 10) * qpow(a, b[u]) % mod;
    }
    public int qpow(int a, int b) {
        int ans = 1;
        a %= mod;
        while (b != 0) {
            if ((b & 1) != 0) ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return ans;
    }
}