GESP 八级 · GESP 202606 C++ 八级 第 20 题

快速幂通过二进制拆分指数，可以在 $O(\log b)$ 时间内计算 $a^b \mod m$。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】算法效率｜时间复杂度｜二进制拆分

1.考纲定位 GESP 八级《算法效率》模块必考内容。命题人专挑学生在"能写代码"和"说清复杂度"之间的认知断层——会敲快速幂的人未必理解为什么是 log 级，这题就是来卡住这个知识盲点的。

2.解题思维 看到"快速幂"先反应二进制拆分：把指数 b 写成二进制，每遇到一个 1 就多乘一次 a 的幂次。因为二进制位数是⌊log₂b⌋+1，乘法次数显然 O(log b)。mod m 只是每次乘法后取模，不改变复杂度量级。

3.陷阱拆解 错项 B 通常让考生误选成 O(b) 或 O(n)。命题人利用两个思维盲区：一是把指数当成循环次数（线性思维），二是混淆 n 与 b 的含义（n 是指数位数，b 是指数本身）。如果你只背结论、不理解二进制分解的本质，就会掉进这个陷阱。

4.反命题思维 若改成"快速幂需要多少次乘法？"或"空间复杂度是多少？"，答案会分别变成⌊log₂b⌋+1 和 O(1)。刷到类似题先问自己：命题人想考我什么——复杂度、乘法次数、还是空间？