快速幂

作者：张帅

问题背景：

计算 a^n时：

朴素算法：连乘 n 次，时间复杂度为 O(n)。

快速幂：利用分治思想和二进制分解，将时间复杂度优化到 O(log⁡n)。

实现：

快速幂思想其实很简单，就是公式的转换

1、当指数是偶数时，我们可以让指数除以2，底数乘以底数

2、当指数是奇数时，我们可以将指数变为偶数

int qmi(int x,int k){
    int res=1;
    while(k)
    {
        if(k&1)res=res*x;
        k>>=1;
        x=x*x;
    }
    return res;
}