题目链接

算法竞赛进阶指南-1.a^b

Method : 位运算-二进制拆分

基础位运算，本题是快速幂的模板题。

注意两点:

1. 有取模运算时不要用自乘*=， 否则会影响计算顺序
2. return 时也要取模， 防止极端例子:n = 0且p = 1

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL a, b, p;

LL fast_pow(LL x, LL n) {
    LL res = 1LL;
    while (n) {
        if (n & 1) {
            res = res * x % p;
        }
        x = x * x % p;
        n = n >> 1;
    }
    return res % p;
}

int main() {
    cin >> a >> b >> p;
    cout << fast_pow(a, b) << endl;
    return 0;
}

复杂度分析

• 时间复杂度${O(log_2n)}$， 其中$log_2n$为对n进行二进制拆分的时间复杂度。

• 空间复杂度${O(1)}$。