LeetCode 12.5每日一题

372. 超级次方

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

a^b=(a^(b/10))^10*a^(b%10)

每次算最后一位，前面的递归处理，从最后一位倒置处理

class Solution {
    int MOD = 1337;
    //计算的过程，b从尾到头计算幂，去掉最后一位，计算最后一位的幂，再考虑前面所有位的dfs值^10,*最后一位的幂%MOD
    public int superPow(int a, int[] b) {
        return dfs(a, b, b.length - 1);
    }
    int dfs(int a, int[] b, int u) {
        if (u == -1) return 1;//u==0,自然返回1
        return (pow(dfs(a, b, u - 1), 10)%MOD * pow(a, b[u]) % MOD)%MOD;
    }
    int pow(int a, int b) {
        int ans = 1;
        a %= MOD;
        while (b-- > 0) ans = ans * a % MOD;
        return ans;
    }
}