GESP 八级 · GESP 八级样题（C++ 组） 第 5 题

对正整数 $a$ 和 $n$（$n$ 为 $2$ 的正整数次幂），下面求 $a^n$ 值的方法是（ ）。 

这题别被‘快速幂’带跑偏，看到n是2的幂，直接想倍增：a^n就是不断平方a^2、a^4、a^8……每次让指数翻倍，O(log n)次乘法搞定。

多数学生会死记‘快速幂用二进制拆分’，看到n=2^k反而犹豫要不要用通用快速幂，结果绕远；还有人把‘折半’‘二分’‘迭代’这些通用算法名硬套到幂运算上，忽略题干‘n为2的正整数次幂’这个倍增法的先决条件，导致选错。

【考点】倍增法｜对数时间复杂度｜快速幂

1. 考纲定位 本题锁定GESP八级C++组“算法设计”模块，命题人卡住的是考生对“计算复杂度”的直觉。GESP大纲明确要求掌握O(log n)算法，这道题就是专门用来区分“会写循环”和“懂快速幂”的分水岭——绝大多数考生会盯着题目里“n是2的正整数次幂”这个条件发呆，完全没意识到这是倍增法的典型特征。

2. 解题思维 看到a^n求值，第一反应是“怎么算最快”。关键观察：n是2的幂，意味着n=2^k，因此a^n=a^(2^k)可以通过不断平方得到：先算a^2，再平方得a^4，再平方得a^8……每次运算让指数翻倍。这正是倍增法的核心——用O(log n)次乘法完成O(n)次幂。通法提炼：凡是底数不变、指数为2的幂次的幂运算，优先想倍增；同考点迁移到“快速幂求a^b”（b为任意整数）时，只需改成二进制拆分指数，原理一致。

3. 陷阱拆解

• A项“折半”：命题人借用了分治法的字面意思，但分治是“把问题分成两半分别求解再合并”，本题没有“合并”步骤，纯平方递推，偷换概念。
• B项“二分”：二分搜索解决的是“在有序数组中找目标”，和幂运算毫无关系，属于张冠李戴。
• D项“迭代”：迭代是通用术语，O(n)次乘法也是迭代，命题人故意放这个选项，考你“能不能区分普通迭代和优化迭代”。

最阴险的细节在题干“n为2的正整数次幂”——这是倍增法的先决条件。如果你只背结论“快速幂用二进制”，看到这道题会犹豫要不要用通用快速幂，反而绕远。

4. 反命题思维 如果改成“n为任意正整数”，答案还是倍增，但需要配合二进制拆分（即快速幂的通用版）；如果改成“求n! mod m”，倍增就失效了，命题人就会考阶乘的线性递推或记忆化搜索。记住：任何“指数是2的幂”的幂运算题，第一眼就想倍增；任何“指数是任意整数”的幂运算题，第一眼想二进制快速幂。

5. 考频与趋势 “倍增”在题库共考过1295题，覆盖11个级别，逐年分布：2008年1题、2011年1题、2019年3题、2023年287题、2024年413题、2025年401题、2026年109题、null年80题；分赛事：GESP一级332题、二级283题、三级215题、四级186题、七级91题、八级79题、六级78题、五级23题、CSP提高级3题、入门级3题、NOIP初赛2题，属于高频基础考点。 “快速幂”共考8题，覆盖3个级别（2009-2026），逐年分布：2009年1题、2017年1题、2021年1题、2023年2题、2025年1题、2026年2题；分赛事：CSP提高级3题、GESP八级3题、NOIP初赛2题，是近年GESP八级重点考查的算法优化点。

6. 预测 基于现有数据，GESP八级未来仍大概率会围绕“指数为2的幂”的倍增与“任意指数”的二进制快速幂交替出题，以检验考生对O(log n)优化思想的掌握。暂无足够依据预测更细的变体（如模运算、负指数等），因为题库中相关题目样本太少。