快速幂

概念讲解

什么是快速幂？

快速幂是快速计算 $a^n$ 的算法，时间复杂度 $O(\log n)$。

核心思想

将指数用二进制表示：

$$a^{13} = a^{1101_2} = a^8 \times a^4 \times a^1$$

实现

迭代实现

123456789long long quickPower(long long a, long long n) {
    long long result = 1;
    while (n > 0) {
        if (n & 1) result *= a;
        a *= a;
        n >>= 1;
    }
    return result;
}

取模快速幂

12345678910long long quickPowerMod(long long a, long long n, long long mod) {
    long long result = 1;
    a %= mod;
    while (n > 0) {
        if (n & 1) result = result * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return result;
}

考点分析

初赛考查方式

1. 选择题： 快速幂原理
2. 程序阅读： 快速幂程序
3. 编程题： 大数幂运算

常见考点

• 快速幂原理
• 取模运算
• 时间复杂度

例题精讲

例题 1：快速幂

题目： 求 $2^{10}$。

解答：

10 = 1010₂
2^10 = 2^8 * 2^2 = 256 * 4 = 1024

例题 2：取模快速幂

题目： 求 $2^{10} \mod 1000$。

解答：

$2^{10} = 1024$，$1024 \mod 1000 = 24$

练习题

1. 快速幂的时间复杂度是多少？

2. 为什么要取模？

3. 快速幂的核心思想是什么？

易错点

⚠️ 注意：

1. 快速幂是 O(log n)
2. 取模可以防止溢出
3. a^0 = 1
4. 注意底数也要取模