Super Pow

https://leetcode.com/problems/super-pow/description/

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Thoughts

https://discuss.leetcode.com/topic/50489/c-clean-and-short-solution 由于给的power是数组形式, 暗示我们要一位一位的处理. 由于ab % k = (a % k) (b % k) % k. 我们因此可以得到a ^ 1234567 % k = (a ^ 1234560 % k) (a ^ 7 % k) % k. 即 f(a, [1234567]) = f(f(a, [123456]), 10) f(a, 7) % k 也就是说我们每次把最后一位拆出来单独运算, 剩下的继续递归. 我们在算f(a, 7)时为了防止出现溢出, 不采用先连乘再mod的直观方法, 而是继续用我们刚提到的ab % k = (a % k) (b % k) % k.

Code

class Solution {
    public int powMod(int a, int b, int k) {
        a %= k; // 防止res * a溢出  
        int res = 1;
        for (int i = 0; i < b; i++) {
            res = (res * a) % k; // 防止res * a溢出  
        }
        return res;
    }

    public int superPow(int a, int[] b, int bLen, int k) {
        if (bLen == 0) {
            return powMod(a, b[0], k);
        }

        return powMod(superPow(a, b, bLen - 1, k), 10, k) * powMod(a, b[bLen], k) % k;
    }

    public int superPow(int a, int[] b) {
        return superPow(a, b, b.length - 1, 1337);
    }
}

Analysis

时间复杂度O(N), N为b长度, 一共要抛出N次, 每次要对抛出的那位计算一下pow, 由于最大才9次, 可以看作O(1), 还有powMod(superPow(a, b, bLen - 1, k), 10, k), 每位连乘十次, 也是O(1).