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 );                 // 从最后一位开始}
};