快速幂算法原理与竞赛应用详解

1. 快速幂算法基础解析

快速幂算法（Fast Exponentiation）是解决大数幂运算的高效方法，在信息学竞赛中属于必须掌握的数学工具。传统幂运算的时间复杂度是O(n)，而快速幂通过二分思想将其优化到O(log n)，这在处理1e9+7这类大数取模运算时优势尤为明显。

1.1 算法核心思想

快速幂基于以下数学原理：

• 当指数为偶数时：a^b = (a^(b/2))^2
• 当指数为奇数时：a^b = a * a^(b-1)

以计算3^13为例：

1. 13是奇数：3 * 3^12
2. 12是偶数：(3^6)^2
3. 6是偶数：(3^3)^2
4. 3是奇数：3 * 3^2
5. 2是偶数：(3^1)^2
6. 1是奇数：3 * 3^0

1.2 基础实现模板

cpp复制long long fastPow(long long base, long long power, long long mod) {
    long long result = 1;
    while (power > 0) {
        if (power % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        power = power / 2;
    }
    return result;
}

注意：在竞赛中必须处理取模运算，否则大数会溢出。mod参数在不需要取模时可设为LONG_LONG_MAX。

2. CSP-S竞赛中的典型应用场景

2.1 数论问题求解

快速幂常用于解决：

• 模逆元计算（费马小定理）
• 矩阵快速幂解递推关系
• 组合数取模运算

例如计算组合数C(n,m) mod p：

cpp复制// 预处理阶乘和逆元阶乘
fact[0] = 1;
for (int i = 1; i <= n; i++) {
    fact[i] = (fact[i-1] * i) % MOD;
}
invFact[n] = fastPow(fact[n], MOD-2, MOD); // 费马小定理
for (int i = n-1;