快速幂

递归快速幂

\[ a_n=\left\{ \begin{aligned} & a^{n-1}×a & (\ \text{if }n\text{ is odd}\ )\\ & a^{n/2}×a^{n/2} & (\ \text{if }n\text{ is even but not 0}\ )\\ & 1 & (\ \text{if }n=0\ )\\ \end{aligned} \right. \]

int qpow(int a,int n){
    if(n==0) return 1;
    if(n%2==1) return a*qpow(a,n-1);
    int tmp=qpow(a,n/2);
    return tmp*tmp;
}

非递归快速幂

先将幂写成二进制，并拆分为除最高位外其他位都是 0 的幂之积

\[ x^{10}=x^{(1010)_2}=x^{(10)_2}\cdot x^{(1000)_2} \]

\[ x^{15}=x^{(1111)_2}= x^{(1)_2}\cdot x^{(10)_2}\cdot x^{(100)_2}\cdot x^{(1000)_2} \]

对于除最高位外其他位都是 0 的幂，我们可以通过不断平方底数求得

\[ x^{(1)_2}=x^1 \]

\[ x^{(10)_2}=x^2 \]

\[ x^{(100)_2}=x^4 \]

\[ x^{(1000)_2}=x^8 \]

所以快速幂还可以写成下面的非递归版本：

int qpow(int a,int n){
    int ans=1;
    while(n){
        if(n&1) ans*=a; // 当前末位为 1
        a*=a; // 不断平方
        n>>=1; // 抹掉末位
    }
    return ans;
}

泛型快速幂

非递归版本：

template<typrname T>
T qpow(T a,T n){
    T ans=1; // 赋值为乘法单位元
    while(n){
        if(n&1) ans=ans*a; // 不用 *=，否则还得重载 *=
        a=a*a;
        n>>=1;
    }
    return ans;
}

评论