超级次方（递归+快速幂）

372 超级次方

传送门：https://leetcode-cn.com/problems/super-pow/

Problem

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

数据范围

1 <= a <= 2^31 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

思路

今天也是抄三叶姐姐题解的一天，真好~

$a^k=a^{(k/1010)+k \mod10}=a^{k/1010}a^{k \mod10}=(a^{k/10})^{10}a^{k\mod10}$

举个例子

$15^{1234}=15^{1230}*15^4$

$15^{1234}=(15^{123})^{10}*15^4$

出现了递归子结构，最后需要实际计算的次方小于10。

递归+快速幂

class Solution {
public:
    // 9.21-9.35
    int MOD=1337;
    int superPow(int a, vector<int>& b) {
        int k=b.size()-1;
        return dfs(a,b,k);
    }
    int dfs(int a,vector<int>& b,int k){
        // 递归终止条件
        if(k==-1) return 1;
        // 前半部分需要递归计算，最后一位直接可以求出
        return pow(dfs(a,b,k-1),10)*pow(a,b[k])%MOD;
    }
    int pow(long long a,int b){
        long long ans=1;
        while(b){
            if(b&1){
                ans=(ans*a)%MOD;
            }
            a=a*a%MOD;
            b>>=1;
        }
        return ans;
    }
};

迭代+快速幂

$15^{1234}=15^{1230}*15^4$

$15^{1234}=(15^{123})^{10}*15^4$

$15^{1234}=((15^{12})^{10}15^3)^{10}15^4$

$15^{1234}=(((15^1)^{10}15^2)^{10}15^3)^{10}*15^4$

迭代版本更加好理解一些~

class Solution {
public:
    // 9.37-10.17 迭代版本
    int MOD=1337;
    int superPow(int a, vector<int>& b) {
        long long ans=1;
        for(int i=b.size()-1;i>=0;i--){
            ans=(ans*pow(a,b[i]))%MOD;
            a=pow(a,10);
        }
        return ans;
    }
    int pow(long long a,int b){
        long long ans=1;
        while(b){
            if(b&1){
                ans=ans*a%MOD;
            }
            a=a*a%MOD;
            b>>=1;
        }
        return ans;
    }
};