#sx004. 快速幂

快速幂

快速幂

题目描述

​ 给定两个非负整数 a 和 b,请使用快速幂算法(Fast Power Algorithm) 高效计算 a 的 b 次方(即 a^b)的值。

算法概念

​ 快速幂算法(Fast Power)是一种在 O(log b) 时间内计算 a^b 的高效方法。其核心思想是利用指数的二进制表示,将指数不断折半,底数不断平方,从而大幅减少乘法运算次数。相比直接循环 b 次乘法的 O(b) 复杂度,快速幂在 b 较大时优势极为显著。

算法原理与步骤

  1. 递归终止条件:若指数 b == 0,则 a^0 = 1,直接返回 1。
  2. 若指数 b 为奇数(b % 2 == 1),则 a^b = a × a^(b-1),其中 b-1 为偶数,进一步可转化为 a × (a^2)^(b/2)。
  3. 若指数 b 为偶数(b % 2 == 0),则 a^b = (a^2)^(b/2),即将底数平方,指数折半。
  4. 通过递归调用,每次将指数减半,直到指数为 0 时返回 1,逐层回溯得到最终结果。
  5. 该算法本质上是基于指数二进制展开的分治策略,每一步都将问题规模缩小为原来的一半。

​ 举例:计算 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),本题为基础练习,暂不考虑取模。