快速幂算法（Fast Exponentiation）
**快速幂算法（Fast Exponentiation）**
快速幂算法是一种高效计算大整数幂的方法，其核心思想是通过二分策略将指数分解为二进制形式，将时间复杂度从朴素的O(n)降低到O(log n)。以下是逐步讲解：
---
### 问题描述
计算 \( a^n \)（a的n次幂），其中a为实数，n为非负整数。直接连乘需要n-1次乘法，当n极大时（如\( n = 10^9 \)）效率极低。快速幂通过指数n的二进制表示优化计算过程。
---
### 关键思路
1. **二进制分解指数*
2025-11-10 10:47:40
0