#sx004. 快速幂
快速幂
快速幂
题目描述
给定两个非负整数 a 和 b,请使用快速幂算法(Fast Power Algorithm) 高效计算 a 的 b 次方(即 a^b)的值。
算法概念
快速幂算法(Fast Power)是一种在 O(log b) 时间内计算 a^b 的高效方法。其核心思想是利用指数的二进制表示,将指数不断折半,底数不断平方,从而大幅减少乘法运算次数。相比直接循环 b 次乘法的 O(b) 复杂度,快速幂在 b 较大时优势极为显著。
算法原理与步骤
- 递归终止条件:若指数 b == 0,则 a^0 = 1,直接返回 1。
- 若指数 b 为奇数(b % 2 == 1),则 a^b = a × a^(b-1),其中 b-1 为偶数,进一步可转化为 a × (a^2)^(b/2)。
- 若指数 b 为偶数(b % 2 == 0),则 a^b = (a^2)^(b/2),即将底数平方,指数折半。
- 通过递归调用,每次将指数减半,直到指数为 0 时返回 1,逐层回溯得到最终结果。
- 该算法本质上是基于指数二进制展开的分治策略,每一步都将问题规模缩小为原来的一半。
举例:计算 3^13 的过程。
3^13 → 13 为奇数,计算 3 × 3^12
3^12 → 12 为偶数,计算 (3^2)^6 = 9^6
9^6 → 6 为偶数,计算 (9^2)^3 = 81^3
81^3 → 3 为奇数,计算 81 × 81^2
81^2 → 2 为偶数,计算 (81^2)^1 = 6561^1
6561^1 → 1 为奇数,计算 6561 × 6561^0 = 6561
最终结果为 3 × 81 × 6561 = 1594323,即 3^13 的值。
输入格式
一行两个非负整数 a 和 b,用空格隔开。
输出格式
一行一个整数,表示 a^b 的值。
输入输出样例
3 13
1594323
数据规模与约定
0 ≤ a ≤ 10^6
0 ≤ b ≤ 10^9
结果保证在 int 范围内(即 a^b ≤ 2^31-1)
时间限制:1 秒(快速幂 O(log b),b=10^9 时约 30 次递归,极快)
提示
代码提示:
// 递归快速幂计算 a^b
int fast_pow(int a, int b) {
// TODO: 边界条件,当 b == 0 时返回 1
// 提示:任何数的 0 次方等于 1
// 根据指数奇偶性进行递归
if (b % 2 == 1) {
// TODO: b 为奇数,返回 a * fast_pow(a * a, b / 2)
// 提示:a^b = a × (a^2)^(b/2)
} else {
// TODO: b 为偶数,返回 fast_pow(a * a, b / 2)
// 提示:a^b = (a^2)^(b/2)
}
}
int main() {
cout << fast_pow(a, b) << endl;
}
运用提示:
快速幂的核心思想是“指数折半,底数平方”。每递归一层,指数 b 减半,乘法次数大幅减少。
注意递归终止条件 b == 0,此时无论 a 为何值(包括 a = 0),结果均为 1。
若 b 为奇数,递归返回 a × fast_pow(a*a, b/2);若 b 为偶数,递归返回 fast_pow(a*a, b/2)。这里 b/2 为整数除法,自动向下取整。
由于递归深度为 O(log b),即使 b = 10^9 也仅约 30 层,无需担心栈溢出。
实际应用中,快速幂常用于大数取模场景(如 a^b mod m),本题为基础练习,暂不考虑取模。