题目链接

算法竞赛进阶指南-23.天才ACM

Method : 位运算-二进制拆分

#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)}$。