372. 超级次方

372. 超级次方

• • 题目
  • 算法设计：迭代
  • 算法设计：递归

题目

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

题目不难懂，问题在于 b 是一个非常非常大的数，会溢出。

• 迭代和递归，各有解决方法，记录在下文。

算法设计：迭代

防止溢出，迭代拆解幂。

$a^{1564}$

= $a^4\ast a^{60}\ast a^{500}\ast a^{1000}$

= $a^4\ast (a^{10}{)}^6\ast (a^{100}{)}^5\ast (a^{1000}{)}^1$

int ans = 1;
for (int i = b.size() - 1; i >= 0; i--) {     // 拆分幂
	ans = (ans * pow(a, b[i])) % k;           // a^1564 = a^4 * (a^10)^6 * (a^100)^5 * (a^1000)^1，% k 防止溢出 
	a = pow(a, 10);                           // a^10、a^100、a^1000、a^1000(不会代入计算)
}

 
快速幂：比普通求幂算法要快

int quick_pow(int a, int b) {                     // 快速幂log(N)，普通幂O(N)
	if( b == 0 ) return 1;
	if( b % 2 != 0 )                              // k 是奇数
		return ( a % k * quick_pow( a, b-1 ) ) % k;
    else {                                        // k 是偶数
        int sub = quick_pow( a, b/2 );
        return ( sub * sub ) % k;
    }
}

 
此外，模运算防止溢出：

• 正常模运算：(a × b) % k
• 防溢出模运算：(a % k) * (b % k) % k

class Solution {
    const int k = 1337;

    int pow(int a, int b) {                           // 快速幂log(N)，普通幂O(N)
        if( b == 0 ) return 1;
        if( b % 2 )                                   // k 是奇数
            return ( a % k * pow( a, b-1 ) ) % k;
        else {                                        // k 是偶数
            int sub = pow( a, b/2 );
            return ( sub * sub ) % k;
        }
    }
public:
    int superPow(int a, vector<int> &b) {
        int ans = 1;
        for (int i = b.size() - 1; i >= 0; i--) {     // 拆分幂
            ans = (ans * pow(a, b[i])) % k;           // a^1564 = a^4 + （a^10)^6 + (a^100)^5 + (a^1000)^1，% k 防止溢出 
            a = pow(a, 10);                           // a^10、a^100、a^1000、a^1000(不会代入计算)
        }
        return ans;
    }
};

算法设计：递归

防止溢出，递归拆分幂，分成俩部分：

• 数组末尾 * (数组剩余部分)^10

$a^{1564}$

= $a^4\ast a^{1560}$

= $a^4\ast (a^{156}{)}^{10}$

= $a^4\ast (a^6\ast (a^{15}{)}^{10}{)}^{10}$

= $a^4\ast (a^6\ast (a^5\ast a^{10}{)}^{10}{)}^{10}{)}^{10}$

int next_pow( int a, int i, vector<int>& b ) {        // 递归拆分幂，防止溢出
	if( i == -1 ) return 1;
	return ( quick_pow( a, b[i] ) * quick_pow( next_pow( a, i-1, b ), 10 ) ) % k;
    // 递归拆分幂，分成俩部分：数组末尾 * 数组剩余^10，再合并出俩者的结果 
}

 
此外，模运算防止溢出：

• 正常模运算：(a × b) % k
• 防溢出模运算：(a % k) * (b % k) % k

完整代码：

class Solution {
    int k = 1337;
public:
    int quick_pow(int a, int b) {                     // 快速幂log(N)，普通幂O(N)
        if( b == 0 ) return 1;
        if( b % 2 != 0 )                              // k 是奇数
            return ( a % k * quick_pow( a, b-1 ) ) % k;
        else {                                        // k 是偶数
            int sub = quick_pow( a, b/2 );
            return ( sub * sub ) % k;
        }
    }
    int next_pow( int a, int i, vector<int>& b ) {    // 递归拆分幂，防止溢出
        if( i == -1 ) return 1;
        return ( quick_pow( a, b[i] ) * quick_pow( next_pow( a, i-1, b ), 10 ) ) % k;
        // 递归拆分幂，分成俩部分：数组末尾 * 数组剩余^10，再合并出俩者的结果 
    }
    int superPow(int a, vector<int>& b) {
        return next_pow( a, b.size()-1, b );                 // 从最后一位开始
    }
};