第三章：如何高效进行模幂运算

labuladong如何高效进行模幂运算

372. 超级次方

先把问题分解为子问题

子问题1：如何高效求幂？

对应以下题目：

50. Pow(x, n)

快速幂解析（分治法角度）

• 通过x*x，每次x变为x^2；
• 通过n//2向下取整，n变为原来的一半；
• 当 n 为奇数时，将多出的一项 x 乘入 res

注意：在C++中，int32 变量 n∈[−2147483648,2147483647] ，因此当 n = -2147483648时执行 n = -n会因越界而赋值出错。解决方法是先将 n存入 long 变量 b ，后面用 b 操作即可。

写法1：用while循环并更新结果

class Solution {
public:
    double myPow(double x, int n) {
//        base case，直接返回0
        if (x == 0.0) return 0.0;
//        如果是负数，则转换成正数
         long b = n;
        double res=1.0;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }

        while (b > 0) {
//      如果b是奇数，则把当前x乘到res中，比如2^5=(2*2)^2 * (2*1,此时的1为result)
            if (b % 2 == 1) {
                res *= x;
            }
            x *= x; // 当前x变成x^2,
            b >>= 1; // b右移一位,相当于除以2并向下取整
        }
        return res;
    }
};

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        # 递归结束的条件
        if n==0:return 1
        # 处理n是负数的情况
        if n<0:
            x=1/x
            n=-n
        res=1
        while n>0:
            if n%2==1:
                res*=x
            x*=x
            n=n>>1
        return res

写法2：用递归（更容易理解）

• 根据上面的公式，若n为奇数，则在递归时另外乘以一个x，若n为偶数，则直接递归即可
• 为防止溢出，把int型的_n 转成long型

class Solution {
private:
    double res = 0.0;
public:
    double myPow(double x, int _n) {
        // 把int _n 转成long，防止溢出
        long n = _n;
        // 递归结束的条件：n为0，除不动了。x的0次方为1，返回1
        if (n == 0) return 1;
        // 处理n为负数的情况
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
    // 如果n为奇数，则递归时单独乘以一个x；若为偶数，则直接递归
        res = (n % 2) ? x * myPow(x * x, n / 2 ): myPow(x * x, n / 2); // 整数默认都为地板除        
        return res;
    }
};

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        # 递归结束的条件
        if n==0:return 1
        # 处理n是负数的情况
        if n<0:
            x=1/x
            n=-n
        res=1
        if n%2==1:
            res=self.myPow(x*x,n/2)*x
        else:
            res=self.myPow(x*x,n/2)
        return res

子问题2：如何处理数组指数？

根据上述规律，可以发现，通过递归，可以缩小该问题规模

    superPow(a, [1,5,6,4])
=>  superPow(a, [1,5,6])

因此，子问题2的递归可以写为（注：需要用到子问题1的实现）：

    int superPow(int a,vector<int>b){
//        递归结束的条件（base case）
        if (b.empty()) return 1;
//        取出最后一个元素
        int last=b.back;
        b.pop_back();
//        缩小规模
        int part1= myPow(a,b);
        int part2= myPow(superPow(a,b),10);
        return part1*part2;
    }

子问题3：如何处理mod运算？

在mod运算时，(a * b) % k = (a % k)(b % k) % k。也就是：对乘法的结果求模，等价于先对每个因子都求模，然后对因子相乘的结果再求模。
因此，在子问题1和2中，把各个因子（也就是幂运算的底）和有乘法的地方添加上mod运算即可。

• 根据题意，把子问题1各处的double类型的pow适当调整int，才能进行mod （比如说double和long等类型就不支持mod运算）

本题完整的代码为：

//#include <vector>
//#include <iostream>
//using namespace std;

class Solution {
private:
    int res = 0.0;
    int base = 1337;
public:
    int myPow(int x, int n) {
//        把int _n 转成long，防止溢出
//        long n = _n;
//        递归结束的条件：n为0，除不动了
        if (n == 0) return 1;
//        处理n为负数的情况
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }

        x %= base;
//        如果n为奇数，则递归时单独乘以一个x；若为偶数，则直接递归
        int b = n % 2;
        res = (b == 1) ? (x * myPow(x * x, n / 2)) % base : myPow(x * x, n / 2);
        return res;
    }

    int superPow(int a, vector<int> b) {
//        递归结束的条件（base case）
        if (b.empty()) return 1;
//        取出最后一个元素
        int last = b.back();
        b.pop_back();
//        缩小规模
        int part1 = myPow(a, last);
        int part2 = myPow(superPow(a, b), 10);
        return (part1 * part2) % base;
    }

};

//int main() {
//    int a = 2147483647;
//    vector<int> b{2, 0, 0};
//    Solution s;
//    int ans = s.superPow(a, b);
//    cout << ans << endl;
//}

class Solution(object):
    def __init__(self):
        self.res=0
        self.base=1337
    def myPow(self, x, n):
        # 快速幂，base case
        if n==0:return 1
        # 处理n是负数的情况
        if n<0:
            x=1/x
            n=-n
        x=x%self.base
        res=1
        while n>0:
            if n%2==1:
                res*=x
            x*=x
            n=n>>1
        return res



    def superPow(self, a, b):
        if not b: return 1
        last=b.pop()
        part1=self.myPow(a,last)
        part2=self.myPow(self.superPow(a,b),10)
        return part1*part2%self.base


# a=2
# b=[3]
# so=Solution()
# print(so.superPow(a,b))

遗留问题：如果是递归计算快速幂myPow，则LeetCode可以通过，本地编译报错。WHY？

class Solution(object):
    def __init__(self):
        self.res=0
        self.base=1337
    def myPow(self, x, n):

    # 递归结束的条件
    if n==0:return 1
    # 处理n是负数的情况
    if n<0:
        x=1/x
        n=-n
    x=x%self.base
    return self.myPow(x*x,n/2) if n%2==0 else self.myPow(x*x,n/2)*x%self.base

def superPow(self, a, b):
    if not b: return 1
    last=b.pop()
    part1=self.myPow(a,last)
    part2=self.myPow(self.superPow(a,b),10)
    return part1*part2%self.base

a=2

b=[1,0]

so=Solution()

print(so.superPow(a,b))

```