快速幂

---

当计算 $x^n$ 时，利用常规的方法，我们是让 $x$ 相乘 $n$ 次。

#include
typedef long long LL;
LL pow(LL x,LL n)
{
     LL res=1;
     for(int i=0; i<n; i++){
         res *= x; // res=(res*x)%Max;
     }
     return res;
}
int main()
{
     LL a, b;
     scanf("%I64d %I64d",&a,&b);
     printf("%I64d",pow(a,b));
     return 0;
}

利用快速幂快速求 $x^n$ 的原理是：

$$x^n = \begin{cases} x^\frac{n}{2} x^\frac{n}{2}, & \text{if $n\%2==0$} \\[2ex] xx^\frac{n}{2} x^\frac{n}{2}, & \text{if $n\%2==1$} \end{cases}$$

可以直接利用位操作（按位与、右移）来实现对$n$的操作
$\rightarrow$ 当$n$为奇数时，$n$的二进制最低位为1，则执行$res*x$操作
$\rightarrow$当$n$为偶数时，$n$的二进制最低位为0，则执行$x*x$操作(从最低位开始操作，所以是$x*x$，而不是$x^\frac{n}{2} x^\frac{n}{2}$)
$\rightarrow$ 每操作一次，$n$都减半，即$n$向右移一位

#include<stdio.h>
typedef long long LL;
LL pow(LL x,LL n)
{
    LL res=1;
    while(n>0)
    {
        if(n & 1){
            res=(res*x);  // res=(res*x)%Max;
        }  
        x=x*x;  // x=(x*x)%Max;
        n >>= 1;
    }
    return res;
}
int main()
{
    LL a, b;
    scanf("%I64d %I64d",&a,&b);
    printf("%I64d",pow(a,b));
    return 0;
}

时间复杂度

$$T(n) = log_2n$$

---