c++怎么实现快速幂算法_c++高效数学运算【干货】

云瑶君_7741

云瑶君_7741

2026-02-08

758人浏览

原创

快速幂通过二进制拆分将时间复杂度从O(n)降至O(log n),核心是底数平方、指数右移、按位累乘;需注意取模时机、边界处理(如n=0)、溢出防护及负指数/浮点数的特殊处理。

c++怎么实现快速幂算法_c++高效数学运算【干货】

快速幂的核心思想是二进制拆分

直接算 a^n 是 O(n) 时间,而快速幂利用 n 的二进制表示,把乘法次数降到 O(log n)。比如 3^13 = 3^8 × 3^4 × 3^1,因为 13 的二进制是 1101,只对每一位为 1 的位置累乘对应幂次。

关键不是“快”,而是避免中间结果溢出和重复计算 —— 每次迭代都把底数平方、指数右移,同时按位判断是否要乘入结果。

递归写法简洁但要注意栈深和取模时机

递归版本容易理解,但 C++ 默认栈空间有限,n 超过 1e6 可能爆栈;另外,如果题目要求取模(如 1e9+7),必须在每次乘法后立刻 % MOD,否则 long long 也可能溢出。

  • if (n == 0) return 1 % MOD; —— 别漏掉 0 次方的边界
  • long long half = quick_pow(a, n >> 1); —— 用右移代替除法更安全
  • return n & 1 ? (half * half % MOD) * a % MOD : half * half % MOD; —— 先平方再乘 a,顺序不能反

迭代写法更推荐用于生产或大指数场景

迭代版空间 O(1),无递归开销,也更容易插入调试逻辑或中断条件。核心是维护当前幂值 base 和结果 res,逐位处理 n 的二进制位。

C++14
C++14

C++14 对 C++11 的修正与增强版本,适合旧系统维护和较老工具链兼容。

下载
  • 初始化:long long res = 1, base = a % MOD; —— 底数先取模防初始溢出
  • 循环条件:while (n > 0),别用 n != 0(负数会出问题,但指数通常非负)
  • 判断最低位:if (n & 1) res = res * base % MOD;
  • 更新:base = base * base % MOD;,n >>= 1;

注意:所有乘法都要套 % MOD,哪怕你用了 long long —— 1e9+7 平方就超 9e18,而 long long 最大约 9.2e18。

处理负指数或浮点底数需额外封装

标准快速幂针对非负整数指数设计。若遇到负指数(如 a^(-n)),得先求 a 在模意义下的逆元(仅当 MOD 是质数且 a 不被整除时可用费马小定理),再对 |n| 快速幂;浮点数则不能直接取模,需去掉 % MOD 部分,但要注意精度丢失和 overflow 风险。

真正容易被忽略的是:很多题中 a 本身可能为 0 或 1,或 n 为 0 —— 这些边界在迭代/递归里都得自然覆盖,别靠特判补救。

C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!

相关文章

c++速学教程(入门到精通)
c++速学教程(入门到精通)

c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
while的用法
while的用法

while的用法是“while 条件: 代码块”,条件是一个表达式,当条件为真时,执行代码块,然后再次判断条件是否为真,如果为真则继续执行代码块,直到条件为假为止。本专题为大家提供while相关的文章、下载、课程内容,供大家免费下载体验。

2023.09.25

374

5

堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

2023.07.18

7347

5

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

2023.08.10

2988

6

overflow什么意思
overflow什么意思

overflow是一个用于控制元素溢出内容的属性,当元素的内容超出其指定的尺寸时,overflow属性可以决定如何处理这些溢出的内容。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.08.15

3220

3

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7436

4

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

0

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

0

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

0

8

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
GDB Reference Card
GDB Reference Card

共0课时 | 0人学习

《Debugging with GDB》用户手册
《Debugging with GDB》用户手册

共0课时 | 0人学习

Valgrind FAQ
Valgrind FAQ

共0课时 | 0人学习