【例84.1】 取余运算

解题思路

二进制快速幂：当前指数最低位1时把当前底数乘入答案，底数每轮平方，指数右移，所有乘法均模k。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

k=1时结果0；指数0时为1%k；保留指定表达式输出格式。

复杂度

时间O(log p)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long b, p, k;
    cin >> b >> p >> k;
    long long base = (b % k + k) % k, e = p, ans = 1 % k;
    while (e) {
        if (e & 1)
            ans = ans * base % k;
        base = base * base % k;
        e >>= 1;
    }
    cout << b << "^" << p << " mod " << k << "=" << ans << "\n";
    return 0;
}