思路与算法

将指数b按二进制拆分，维护result和当前底数a。初始a取模m，result=1 mod m。

当b的最低位为1时，将result乘a后取模；然后将a平方取模，并把b右移一位。重复直到b变为0，输出result。输入允许m=1，此时全部余数均为0，因此初始值也按m取模。

正确性说明

循环保持不变量：result乘以当前a的b次方，与原始A的B次方模m同余。初始显然成立。若b=2q+r，其中r为0或1，更新后result乘入a^r，底数变为a^2，指数变为q，乘积仍为原来的result*a^(2q+r)，所以不变量保持。

循环结束时b=0，所求余数就是result。所有更新均取模，使result处于0..m-1，因此输出的是规范余数。

复杂度

初始化O(1)。指数每轮减半，b≤10^9时至多30轮，每轮常数次乘法和取模，总时间O(log(b+1))，额外空间O(1)。

易错点

只输出数值，不输出a^b mod m=之类前缀，这与旧格式化模板的输出协议不同。m为正所以取模合法；m=1应输出0。a取模后小于10^9，两个模内数乘积小于10^18，使用long long保存乘积即可，不能用32位int相乘。先根据当前指数位累乘，再平方底数和右移指数。

参考代码（C++11）

#include <iostream>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a, b, m;
    cin >> a >> b >> m;
    a %= m;
    ll result = 1 % m;
    while (b) {
        if (b & 1)
            result = result * a % m;
        a = a * a % m;
        b >>= 1;
    }
    cout << result << '\n';
}