二分快速幂模板分治：50.pow(x,n) 372.超级次方 1808.好因子的最大数目

二分快速幂模板//分治：50.pow(x,n) 372.超级次方 1808.好因子的最大数目

首先，介绍二分快速幂（取模可有可无，都叫快速幂）的模板：

typedef long long ll;
ll qspowmod(ll a,ll b,ll c){      //递归写法
    if(b==0)return 1%c;
    ll res=qsmi(a*a%c,(b>>1),c);
    if(b&1) res=res*a%c;
    return res;
}

typedef long long ll;
ll qspowmod(ll a,ll b,ll c){    //非递归写法
ll res=1%c;
a%=c;                        
while(b){
if(!b&1){
res=(res*a)%c;
}
a=(a*a)%c;
b>>=1;
}
return res;
}

本质原理：模运算的一条运算规则：（m*n)%c=(m%c)(n%c)%c;

对应的：（m*m)%c=(m%c)^2%c;

对应的思想：分治，二分求解（算法初学者一定要多多画图，调试，推演

详细讲解：

夜深人静写算法（三十）- 二分快速幂_英雄哪里出来-CSDN博客

例题1：pow(x,n)

 分析：

 

 对于C++使用者来说，C++大而全的高效模板函数（从C继承的一堆库函数，独立发展的STL）可以极大地便利问题求解。

可，我们的目的是什么。一个解题者追求的不仅仅是简单的AC，他追求的是极致的解答。

卡一下BUG，AC过去，只能是竭泽而渔。

这也是为什么很多老师在教C++学习者学算法和数据结构时，不推荐STL，而是要求自创。

一是系统模板大而全，缺乏精准，用起来不方便。二是，只有用自己的算法，跳出既定的框架，主动思考，才能真真正正地提高自己的算法能力，在编程这条路上走得长远。

所以：

class Solution {
public:
typedef long long ll;
double qsmi(double x,int n){
    if(n==0)return 1.00000;
    double res=qsmi(x,n/2);
    res*=res;                   //很明显，该代码只是对篇首的模板变化了一下
    if(n&1) res=res*x;          //一样的AC，不一样的骄傲
    return res;
}
    double myPow(double x, int n) {
    return (n>0)?qsmi(x,n):qsmi(1.0/x,n);
    }
};

总结：快速幂是算法入门的基本，从中以深刻理解分治思想。

例题二：372.超级次方

一开始想到扩展欧拉公式。

夜深人静写算法（三十三）- 扩展欧拉定理_英雄哪里出来-CSDN博客

幸好，本题的b用动态数组给出，我们可以对b的每位逐一攻克，最后再合并相乘。

（分治算法：分解原问题->解决子问题->合并问题解）

class Solution {
public:
typedef long long ll;
const int mod=1337;
ll qsmi(int a, ll b,ll mod) {
    ll jie = 1;
    while (b > 0) {
        jie %=mod;
        if (b & 1) jie = (jie * a) %mod;       
        b >>= 1;
        a = (a%mod)*(a%mod)%mod;//注意，这里要再用一次模乘性质，否则会溢出
    }
    return jie % mod;
}
    int superPow(int a, vector& b) {
    ll k=a;
    if(b.empty())return 1;
    int las=b.back();
    b.pop_back();
    ll th1=qsmi(a,las,mod);               //分别抽离b的最后一位，递归分治
    ll th2=qsmi(superPow(a,b),10,mod);
    return th1*th2%mod;
    }
};

（其他题解大致思路相似，关键是分治（二分）算法的理解 ，和溢出问题的解决。

例题三：好因子的最大数量（注：这是道数学题）

 算法起步篇（力扣）：1492.n的第n个因数 1362.最接近的因数 1808 好因子的最大数目_0_uL<解题者1的博客-CSDN博客

行远自弥，登高自卑。大家加油啊。