LeetCode刷题【372】超级次方

输入：a = 2, b = [3]
输出：8

输入：a = 2, b = [1,0]
输出：1024

输入：a = 1, b = [4,3,3,8,5,2]
输出：1

输入：a = 2147483647, b = [2,0,0]
输出：1198

快速幂使用，注意识别中途取余的情况
先了解下快速幂相关的知识，可以尝试下做下剑指 Offer 16. 数值的整数次方

另外一个知识点同底数幂相乘,底数不变,指数相加即 a^m * a^n = a^(m+n)

分析

所以当我们面对int[] b次幂的时候，即等同于

a^(b[0] * 100...0) * ... * a^(b[i])

举个栗子假设int[] b为[2,3,4]

那么结果即为a^200 * a^30 * a^4 等同于
a^(100+100) * a^(10+10+10) * a^4
a^100 * a^100 * a^10 * a^10 * a^10 * a^1 * a^1 * a^1 * a^1
最终我们可以得到
(a^100)^2 * (a^10)^3 * (a^1)^4

这样我们从末位开始往前遍历，中间可以重复利用 a^(10^n)的结果

自定义快速幂函数pow(int a, int b)中注意处理各种要取模的情况

代码

class Solution {
    int mod = 1337;

    public int superPow(int a, int[] b) {
        int ans = 1;
        for (int i = b.length - 1; i >= 0; i--) {
            ans *= pow(a,b[i]);
            ans %= mod;
            a = pow(a,10);
        }
        return ans;
    }


    public int pow(int a, int b){
        if (b==0) return 1;
        if (b==1) return a%mod;
        int ans = pow(a,b/2);
        return ((ans * ans)%mod) * pow(a,b%2) % mod;
    }
}