文字教学

本题要求计算 $a^b \bmod p$，但 $a, b$ 都可能非常大（最大 $2^{31}-1$），直接计算 $a^b$ 后再取模完全不可行，必须使用快速幂（也称二分幂）。

快速幂的基本思想：利用指数的二进制表示，将幂次折半。例如计算 $a^b \bmod p$：

• 若 $b = 0$，结果为 $1 \bmod p$。
• 否则维护一个底数 base = a % p 和结果 res = 1。
• 循环，每次判断 $b$ 的最低位：
  • 若为 $1$，则 res = (res * base) % p；
  • 然后将 base 平方后取模：base = (base * base) % p；
  • 将 $b$ 右移一位。
• 当 $b$ 变为 $0$ 时结束，res 即为答案。

这种方法每次将指数规模减半，时间复杂度为 $O(\log b)$，可以轻松应对 $b$ 在 int 范围的情况。运算过程中乘法可能会超出 int 范围，需要用 long long 过渡。

参考代码

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

int main() {
    int a, b, p;
    cin >> a >> b >> p;
    ll base = a % p, res = 1 % p;
    int e = b;
    while (e) {
        if (e & 1) res = (res * base) % p;
        base = (base * base) % p;
        e >>= 1;
    }
    cout << a << "^" << b << " mod " << p << "=" << res << endl;
    return 0;
}