快速幂CSP-J

💡 核心思想

快速幂在 $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$ 的二进制位。每次平方并按位累乘。

🎯 直觉理解

快速幂求 $a^b$，朴素循环乘 b 次是 $O(b)$，b 是 $10^{18}$ 就完蛋；快速幂只要 $O(log b)$。

原理：把指数拆成二进制。$b=13=1101_2$，$a^{13}=a^8 imes a^4 imes a^1$——只需要算 $a^1, a^2, a^4, a^8$（每次平方）四个数，乘起来即可。

代码三行核心：while(b){ if(b&1) ans=ans*a%M; a=a*a%M; b>>=1; }。每次循环：a 自己平方（对应二进制位权重翻倍），b 的当前最低位决定要不要乘进答案。配套记得取模防溢出。矩阵快速幂完全同理，把 a 换成矩阵、乘法换成矩阵乘法，用来加速线性递推（如斐波那契）。

📝 算法流程

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 
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;
}

⚠️ 常见坑点

📚 相关题目