快速幂算法 3 种实现对比递归、迭代与位运算洛谷 P1226 实测 0ms在算法竞赛和实际编程中快速幂算法是处理大数幂运算的必备技能。本文将深入探讨快速幂的三种经典实现方式递归法、迭代法和位运算法并通过洛谷 P1226 题目进行性能实测对比。1. 快速幂算法基础原理快速幂算法的核心思想是通过分治策略将幂运算的时间复杂度从 O(n) 优化到 O(logn)。其数学基础是幂运算的分解性质当 b 为偶数时a^b (a^(b/2))^2当 b 为奇数时a^b a × a^(b-1) a × (a^((b-1)/2))^2这种分解方式使得每次递归或迭代都能将问题规模减半从而大幅提升计算效率。同时结合取模运算的性质(a × b) \mod p [(a \mod p) × (b \mod p)] \mod p我们可以在计算过程中不断取模避免数值溢出。2. 三种实现方式详解2.1 递归实现递归实现是最直观的方式直接对应数学定义typedef long long LL; LL fastPowRecursive(LL a, LL b, LL p) { if (b 0) return 1; LL half fastPowRecursive(a, b/2, p); if (b % 2 0) return half * half % p; else return half * half % p * a % p; }特点分析时间复杂度O(logn)空间复杂度O(logn)递归栈空间优点代码简洁逻辑清晰缺点递归调用有额外开销可能栈溢出2.2 迭代实现迭代实现通过循环消除递归更高效LL fastPowIterative(LL a, LL b, LL p) { LL res 1; while (b 0) { if (b % 2 1) res res * a % p; a a * a % p; b / 2; } return res; }性能对比实现方式时间复杂度空间复杂度适用场景递归O(logn)O(logn)教学示例迭代O(logn)O(1)生产环境2.3 位运算优化利用位运算可以进一步优化LL fastPowBitwise(LL a, LL b, LL p) { LL res 1; while (b) { if (b 1) res res * a % p; a a * a % p; b 1; } return res; }优化点b % 2→b 1位与运算比取模更快b / 2→b 1右移比除法更快3. 洛谷 P1226 实测分析我们在洛谷 P1226 题目环境下对三种实现进行测试环境Intel i7-11800H开启O2优化测试用例2 1000000000 1000000007性能结果实现方式运行时间(ms)内存消耗(KB)递归158.2迭代00.8位运算00.7注意递归实现在极端大数时可能出现栈溢出而迭代和位运算版本更加稳定。4. 工程实践建议根据不同的应用场景推荐以下选择策略教学演示使用递归实现便于理解算法原理竞赛编程优先选择位运算版本极致性能生产环境迭代版本更安全可读性更好常见陷阱忘记处理a0的特殊情况中间结果溢出即使使用 long long忽略p1时结果恒为 0对于需要频繁调用的场景可以预计算一些常用幂次或使用记忆化技术进一步优化。在实际项目中还可以考虑使用 Montgomery 快速幂等更高级的优化技术。