GESP 八级 · GESP202609 C++ 八级 第 5 题

关于快速幂算法，下列说法正确的是（　　）。

快速幂的核心是把指数写成二进制，从低位到高位扫描，遇到 1 就乘一次底数。朴素乘幂要 n 次乘法，二进制拆分后乘法次数变成 O(log n)。负指数需要求逆元，不能直接套用；模数可以是任意正整数；空间复杂度是 O(1) 或递归 O(log n)。

A 错在"任意负指数"——负指数本质是求逆元，算法本身只处理非负；C 错在"只能在质数模数使用"——模运算与质数无关，逆元才需要质数条件；D 错在 O(n)——迭代版常数空间，递归版 O(log n)。

1. 考纲定位

本题考查《GESP 考试大纲》八级"算法与数据结构"模块中的快速幂算法。命题人放这道题，卡住的是考生对算法复杂度分析的模糊认知——很多人背过快速幂的代码，但说不清为什么乘法次数从 O(n) 降到 O(log n)，更分不清负指数、模数限制这些边界条件。

2. 解题思维

看到"快速幂"四个字，先想：二进制拆分。任何正整数 n 都能写成 2^k1 + 2^k2 + … 的形式，a^n = a^(2^k1) × a^(2^k2) × …。朴素乘幂要 n 次乘法，二进制拆分后乘法次数等于 n 的二进制位数，即 O(log n)。

选项 B 说"乘法次数从朴素乘幂时的 n 优化为 log n"，这就是快速幂的核心优化，完全正确。