大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

实现a的b次方的函数。但是给出的b是超级巨大的，而且是用数组保存着每一位的。

解题方法

这个题是 50. Pow(x, n) 的拓展题，都是快速求幂的问题。但是这个题由于结果的数值大，需要模 1337；对于模什么数一般都是瞎选的，不用考虑这个题为什么模 1337。

这个题的难点在于：如何求数组表示的超级大的数字 b 次幂。

求幂也可以边遍历，边求。

比如求 $2^23$ ，其中 23 用数组表示即 $[2, 3]$。

那么：

$2^23 = (2 ^20) (2 ^3) = (2^2)^10 (2^3)$ 。

也就是说把可以遍历数组：

  • 先求 $2 ^2$，把它的结果求一次 10 次幂；
  • 然后把计算结果，再乘以 $2^3$。

需要注意这里每次求幂计算之前和之后都要 $% 1337$。是为了防止数值过大，导致求幂的结果溢出的问题。

先求幂再取模，与先取模再求幂得到的结果是一样的。

三种语言的代码如下：

  1. class Solution {
  2. public:
  3.     const int MOD = 1337;
  4.     int superPow(int a, vector<int>& b) {
  5.         int res = 1;
  6.         for (int x : b) {
  7.             res = pow(res, 10) * pow(a, x) % MOD;
  8.         }
  9.         return res;
  10.     }
  12.     int pow(int a, int b) {
  13.         a %= MOD;
  14.         if (b == 0) {
  15.             return 1;
  16.         }
  17.         if (b % 2 == 1) {
  18.             return a * pow(a, b - 1) % MOD;
  19.         }
  20.         return pow(a * a, b / 2) % MOD;
  21.     }
  22. };
class Solution {
    final int MOD = 1337;
    public int superPow(int a, int[] b) {
        int res = 1;
        for (int x : b) {
            res = pow(res, 10) * pow(a, x) % MOD;
        }
        return res;
    }

    int pow(int a, int b) {
        a %= MOD;
        if (b == 0) {
            return 1;
        }
        if (b % 2 == 1) {
            return a * pow(a, b - 1) % MOD;
        }
        return pow(a * a, b / 2) % MOD;
    }
}

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        res = 1
        for x in b:
            res = self.pow(res, 10) * self.pow(a, x) % 1337
        return res

    def pow(self, a, b):
        if b == 0 or a == 1: return 1
        if b % 2:
            return a * self.pow(a, b - 1) % 1337
        return self.pow((a * a) % 1337, b / 2) % 1337
  • 时间复杂度：$O(N)$，N 是数组的长度。
  • 空间复杂度：$O(N)$，递归用到了栈的深度。

总结

  1. 今天这个题目考了快速幂，偶尔会使用到的技巧，需要掌握。
  2. 做这种结果很大，需要取模的题目时，一定要注意不要溢出。

参考资料
http://www.cnblogs.com/grandyang/p/5651982.html

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。