leetcode-超级次方SuperPow

一、题目

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

示例 1:

输入: a = 2, b = [3]
输出: 8
示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-pow
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、Pow(x, n)

给定一个数，求 n 次方。n 次方可以分解成两个 n/2 次方相乘，所以递归即可。

class Solution
{
    public:
        double myPow(double x, int n)
        {
            bool negative = n < 0;
            double res = helper(x, n);
            return negative ? 1 / res : res;
        }
    
    private:
        double helper(int x, int n)
        {
            if(n == 0)
            {
                return 1;
            }
            if(n == 1)
            {
                return x;
            }

            if(n % 2)
            {
                double res = helper(x, n / 2);
                return res * res *x;
            }
            else
            {
                double res = helper(x, n / 2);
                return res * res;
            }
        }
};

三、Super Pow

同样是求某个数的 n 次方，但是 n 存在数组中，如 [1, 0] 代表 n 为 10。而且数组代表的 n 会非常大，有可能会超过 int 的范围，所以直接还原 n 然后计算 n 次方的方法是行不通的。既然这样，就只能从每位下手，有这样一个公式：

(a * b) % k = (a % k) * (b % k) % k

以数组为 [1, 2, 3, 4, 5, 6, 7] 为例，表示 a 的 1234567 次方，因为有

a ^ 1234567 = (a ^ 1234560) * (a ^ 7)

所以

(a ^ 1234567) % k = (((a ^ 1234560) % k) * ((a ^ 7) % k)) % k

而

(a ^ 1234560) % k = ((a ^ 123456) ^ 10) % k = (((a ^ 123456) % k) ^ 10 ) % k

所以

(a ^ 1234567) % k = (((((a ^ 123456) % k) ^ 10 ) % k) * ((a ^ 7) % k)) % k

将 a ^ n % k 抽象为 f(a, n) 函数，那么上式可以写成

f(a, 1234567) = f(f(a, 123456), 10) * f(a, 7) % k

可以发现，每次都可以把 n 的最后一位去除，从而减少 n，当 n 为 1 或为 0 时返回即可。不过注意上面的式子对于 n 为 [0 : 10] 内的数都不需要再调用 f 函数了，直接求就可以，也就是将外层 f 改为 pown。

f(a, 1234567) = pown(f(a, 123456), 10) * pown(a, 7) % k

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        if(b.empty())
            return 1;
        int back = b.back();
        b.pop_back();
        return pown(superPow(a, b), 10) * pown(a, back) % base_;
    }
private:
    int pown(int n, int k)
    {
        /* 
         * 因为n可能很大，这里实现取模防止在for循环result * n中溢出
         * 比如result为第二次for循环后的某个数，而n为INT_MAX，乘完直接溢出
         */
        n %= base_;
        int result = 1;
        for(int i = 0; i < k; ++ i)
            result = (result * n) % base_;
        return result;
    }

    const int base_ = 1337;
};

参考原文:
每天一道LeetCode—–求一个数的n次方，n是很大很大的数，n用数组存储着