快速幂

聊聊快速幂

今天leetcode正好刷到了，就来写一下吧

快速幂的定义

先放上原题：leetcode50pow（x,n）

顾名思义，快速幂就是一种快速求幂的方法，它能在$O(logn)$时间内求出一个底数的幂，比起朴素的$O(n)$做法快了相当多。关键的是，这种方法适用于相当多的题目中，在算$a^n$时，只要a的数据类型支持乘法结合律就可以用，如矩阵、高精度整数，甚至是一个dp转移的状态，以降低时间复杂度。

快速幂的两种解法

递归解法

递归解法的代码较为简单，缺点是空间复杂度较高，较为耗费栈空间。

class Solution {
public:
    double _myPow(double x, int n) {
        if(n==0)return 1.0;
        double ans=_myPow(x,n/2);//原理就是分治
        return (n&1)==1?ans*ans*x:ans*ans;//判断奇偶
    }
    double myPow(double x, int n){
        double ans=_myPow(x,n);
        if(ans==0)return 0.0;//防止除数是0
        return n<0?1.0/ans:ans;
    }
};

时间复杂度为$O(logn)$，空间复杂度为$O(n)$

迭代解法

考虑到栈空间的损耗，可以采用更为巧妙的迭代解法。

递归解法可以通过判断奇偶来决定是否乘上x,但是迭代解法却难以判断这一点，所以我们需要转换思路，从幂数的二进制表示入手。（这里其实建立在我看过解法之后得出的结论….）

不妨假设我们要计算$x^{39}$，幂数为39，39的二进制表示为100111，而这代表$39=2^5+2^2+2^1+2^0$,因此$$x^{39}=x^{2^5+2^2+2^1+2^0}=x^{2^5}*x^{2^2}*x^{2^1}*x^{2^0}$$

这告诉我们只要按幂数二进制的每一位来迭代，只要该位为1，就代表此位对答案有贡献，要注意的是随着幂数的迭代，贡献也要不断迭代。

class Solution {
public:
    double _myPow(double x, int N) {
        double ans=1.0;
        long long n=abs(N);//这里要注意用正数来算
        while(n>0){
            if((n&1)==1)ans*=x;//判断该位是否为1
            x*=x;//贡献迭代
            n/=2;//不断除于2，以每次通过&来判断最后一位
        }
        return ans;
    }
    double myPow(double x, int n){
        double ans=_myPow(x,n);
        if(ans==0)return 0.0;
        return n<0?1.0/ans:ans;
    }
};

注意点

在多数题目中，题目常常会要求对一个大素数取模，这是因为计算结果可能会非常巨大，但是如果在这里用高精度又过于麻烦。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模，如果MOD较大，还应当开long long。

//递归快速幂（对大素数取模版本）
#define MOD 1000000007
typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a % MOD;
    else
    {
        ll temp = qpow(a, n / 2) % MOD;
        return temp * temp % MOD;
    }
}
//代码来源：https://zhuanlan.zhihu.com/p/95902286

快速幂拓展

快速乘（加法）

题目链接：leetcode29两数相除

此题就是模拟两数相除，看似简单，事实上对于细节的要求相当高。

基本思路：为防止溢出，于是将两数都变为负数来处理（如果用longlong可以在以正数来处理），假设被除数为a，除数为b，答案为ans（正数），则有$ans*b\ge{a},(ans+1)*b\le{a}$。又a,b都为整数，所以ans一定在$[0,\abs{a}]$范围内，我们只要在此区间内二分即可，判断时用加法来实现乘法，即替换快速幂中的乘法。听起来简单，但是如果不用longlong来避免溢出的话，处理起来的细节真滴折磨。

细节：（下面默认$MIN=-2^{31}，MAX=2^{31}-1$）

1. 当a=MIN,b=-1时，会发生溢出，需要特判。
2. 由于代码中不能出现除号，所以二分时mid=left+()(right-left)>>1)
3. 二分时要在mid==MAX时break，以避免left=MAX+1会溢出
4. 快速乘法中，当ret加上n的贡献前，需要先判断是否满足ret+n>=a,否则即return,同样可以防止溢出
5. 在最后一轮循环前的每次循环中，要保证倍增的b倍增后不会大于a，以防止溢出，至于最后一次循环可直接不自增

代码实现：

#define long long ll
#define MIN (1<<31)
#define MAX (1<<30)-1+(1<<30)//你敢信我写个max还得这么写
int dividend,divisor;
class Solution {
public:
    int divide(int _dividend, int _divisor) {
        dividend=_dividend;divisor=_divisor;
        if(dividend==0)return 0;//被除数等于0，直接返回0
        if(dividend==MIN){//防止溢出
            if(divisor==1)return MIN;
            else if(divisor==-1) return MAX;
        }
        if(divisor==MIN)return dividend==MIN?1:0;//顺便防一下这个
        bool flag=(dividend>0&&divisor>0)||(divisor<0&&dividend<0)?true:false;//设个标志位判断最后结果是否为负数
        dividend=-abs(dividend),divisor=-abs(divisor);//都映射到负数域上
        if(flag&&dividend>divisor)return 0;//如果被除数的绝对值小于除数的则直接返回0
        int l=0,r=dividend==MIN?MAX:-dividend;
        int mid,ans=0;
        while(l<=r){
            mid=l+((r-l)>>1);
            if(check(mid)){
                ans=mid;
                if(mid==MAX)break;//防溢出
                l=mid+1;
            }
            else r=mid-1;
        }
        return flag?ans:-ans;
    }
    bool check(int x){
        int ret=0;
        int n=divisor;
        while(x){
            if(x&1==1){
                if(ret<dividend-n)return false;//防溢出
                ret+=n;
            }
            if(x>1){
                if(n<dividend-n)return false;//防溢出
                n+=n;
            }
            x>>=1;
        }
        if(ret>=dividend)return true;
        else return false;
    }
};

下面这段代码是我在大佬的题解中模仿三叶姐的java题解改了改的c++版本，只能说三叶姐yyds。

//由于操作数都是负数，因此自倍增过程中，如果操作数小于 INT_MIN 的一半（-1073741824），则代表发生溢出。
class Solution {
    int MIN = 1<<31, MAX = (1<<30)-1+(1<<30);
    int LIMIT = -1073741824; // MIN 的一半
public:
    int divide(int a, int b) {
        if (a == MIN && b == -1) return MAX;
        bool flag = false;
        if ((a > 0 && b < 0) || (a < 0 && b > 0)) flag = true;
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int ans = 0;
        while (a <= b){
            int c = b, d = -1;
            while (c >= LIMIT && d >= LIMIT && c >= a - c){
                c += c; d += d;//c不断倍增，d相当于商的倍增
            }
            a -= c;
            ans += d;
        }
        return flag ? ans : -ans;
    }
};