快速幂 - GitPress.io

原理讲解

幂运算即求 $a^n$。

最基础的方法是可以通过循环累乘，时间复杂度为 $O(n)$
加速幂运算可以从减少累乘次数入手，合并某些步骤为一步。如果n能被2整除，那么可以先得到 $a^{n/2}$ 的值，再进一步求取 $a^n$，但时间复杂度仍为O(n)。
若能找到 $2^k = n$，原有运算可优化为 $a^{2^{2...}}$ 的形式，仅需k次运算即可完成，但适用范围有限。不过任意整数都可分解为如下形式：$2^{k_1}+2^{k_2}+2^{k_3}+ ... +2^{k_n} = n$。利用递推，即可短时间内求取各项值。而利用二进制性质即可直接得知上述多项式。
- 例：十进制得到11为二进制的1011可表示为 $2^3$+$2^1$+$2^0$，之后便可直接实现快速幂算法。

#include<stdio.h>

int poww(int a, int b) {
    int ans = 1, base = a;
    while(b) {
        if(b&1) {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}

int main() {
    printf("%d\n", poww(2,3));
    return 0;
}