快速幂CSP-S

💡 核心思想

快速幂在 $O(\log n)$ 时间内计算 $a^n \mod p$。核心是将指数按二进制分解：$a^n = a^{b_0 \cdot 2^0} \cdot a^{b_1 \cdot 2^1} \cdot \ldots$，其中 $b_i$ 是 $n$ 的二进制位。每次平方并按位累乘。

🎯 直觉理解

想象你要计算 $2^{13}$。朴素方法是乘 13 次。但 $13 = 1101_2$，所以 $2^{13} = 2^1 \times 2^4 \times 2^8$。你只需要算 $2^1, 2^2, 2^4, 2^8$（每次自乘），然后挑需要的乘起来——总共只需要 $\log 13 \approx 4$ 步。

📝 算法流程

1. 初始化 ans = 1
2. n 的每一位：如果为 1，ans *= a
3. a = a * a（自平方）
4. n >>= 1（右移一位）

$$a^n = \prod_{i: b_i = 1} a^{2^i} \pmod{p}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll a, ll n, ll mod) {
    ll ans = 1; a %= mod;
    while (n) {
        if (n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
int main() {
    ll a, n, p; cin >> a >> n >> p;
    cout << qpow(a, n, p) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目