快速幂

暴力破解

我们很容易想到 $a^b$ 可以采用 b 个 a 相乘来求结果。

但此种方法需要大量计算，时间复杂度为 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    long long ans = 1;
    cin >> a >> b;
    for (int i = 0; i < b; ++i) {
        ans *= a;
    }
    cout << ans << endl;
    return 0;
}
复制代码

快速幂算法

当我们计算 $a^b$ 次方的时候可以利用 $a^b = ({a*a})^{b/2}$ 。

这样每次我们只需要把指数 a 减少一半，底数 b 变为原来的平方即可大大减少循环的次数。

当指数为偶数时，每次把指数 b 缩小为原来的一半，底数 a 变为原来的平方。