🌕🌗 372. 超级次方

难度: 🌕🌗

问题描述

---

解法

class Solution {
    int mod = 1337;
    public int superPow(int a, int[] b) {
        // 思路：
        // 找规律
        // 例：a = 66, b = [7, 8, 9, 0] 即求 66^7890
        // 可转换为 66 ^ 7890 = 66^0 * 66^7890 = 1 * 66^(789*10) = 66^789 * 66^10
        // 进一步转换为 66 ^ 7890 = (66^78 * 66^10 * 66^9)
        // 即每次将数组的最后一位取出，得到结果值后，与数组除去最后一位的结果相乘
        // 直到数组中每个元素均被取出相乘
        int len = b.length;
        return mySol(a, b, len - 1);
    }

    private int mySol(int a, int[] b, int index) {
        // 递归终止条件
        if(index < 0) {
            return 1;
        }
        if(a == 1) {
            return 1; // 虽然初始情况 a != 1, 但不能保证计算过程中出现 a == 1
        }
        int cur = b[index]; // 剔除出来的最后一位
        int res = pow(a, cur);
        int tmp = mySol(a, b, index - 1); // 需要再乘 10 的次方
        tmp = pow(tmp, 10);
        return (res * tmp) % mod;
    }

    // 借助 快速幂 快速得到 x^y，由于 y ∈ [0, 10] 因此也可以不借助快速幂
    private int pow(int x, int y) {
        // 递归终止条件
        if(y == 0) {
            return 1;
        }
        x %= mod;
        if(y == 1) {
            return x % mod;
        }
        if(x == 1) {
            return x;
        }
        // 递归
        if((y & 1) == 1) {
            // y 为奇数
            return (x * pow(x, y - 1)) % mod;
        } else {
            return (pow(x, y / 2) * pow(x, y / 2)) % mod; // 2 个 1337 以内的数相乘肯定在 int 范围内
        }
    }
}

---

输出