当前位置: 首页 > news >正文

快速幂运算

快速幂运算

  • 一、快速幂运算
    • 快速幂运算(Exponentiation by Squaring)
    • 基本思想
    • 算法实现(②③为非递归)
      • ① 递归运算
      • ② 普通 除模运算(不带 **模数** 与 带 **模数**)
      • ③ 按位与运算
    • 使用示例
      • 示例代码
    • 复杂度分析
    • 小结论


一、快速幂运算

快速幂运算(Exponentiation by Squaring)

快速幂运算是一种高效计算 ( b^e ) 的算法,其中 ( b ) 是基数,( e ) 是指数。传统的逐步乘法方法的时间复杂度为 ( O(e) ),而快速幂运算的时间复杂度为 ( O(\log e) ),因此在处理大数时特别有效。

基本思想

快速幂运算的基本思想是利用平方和乘法来减少乘法的次数。其主要依据是:

  • 如果指数 ( e ) 为偶数,则 ( b^e = (b{e/2})2 )
  • 如果指数 ( e ) 为奇数,则 ( b^e = b \times b^{e-1} )

通过这种方式,可以在每次迭代中将指数减半,从而显著降低计算时间。

算法实现(②③为非递归)

以下是使用 JavaScript 实现的快速幂运算的代码:

① 递归运算

/**  不带模数* 快速幂运算* @param {number} base - 基数* @param {number} exp - 指数* @returns {number} */
function quickPow(base, exp) {if (exp === 0) {return 1; // 任何数的零次方为 1}if (exp % 2 === 0) {const half = quickPow(base, exp / 2);return half * half;} else {return base * quickPow(base, exp - 1);}
}

② 普通 除模运算(不带 模数 与 带 模数

/** 不带模数* 快速幂运算* @param {number} a- 基数* @param {number} b- 指数* @returns {number} 计算结果 (a ^ b)*/
function quick (a, b) {let ans = 1while(b) { // 当指数存在的时候// 如果指数是奇数,则要先拉出来一个底数乘到最终结果上,其余步骤和偶数一样操作// 如果指数是偶数,则要底数平方,指数除以2(如果是使用按位与运算,则使用 "b >>= 1")b/2if(b % 2 === 1) ans *= aa *= ab = Math.floor(b / 2) // 注意一定要使用Math.floor(),否则会出现小数点,导致结束循环}return ans
}
console.log(quick(2, 7)) // 128/**  带模数* 快速幂运算* @param {number} base - 基数* @param {number} exp - 指数* @param {number} mod - 模数* @returns {number} 计算结果 (base^exp) % mod*/
const modExp = (base, exp, mod) => {let result = 1; // 初始化结果为 1base = base % mod; // 将基数在模数下取值while (exp > 0) {// 如果 exp 为奇数,将当前的 base 乘入结果if (exp % 2 === 1)  result = (result * base) % mod;// 将 base 平方base = (base * base) % mod;// exp 右移,相当于整除 2exp = Math.floor(exp / 2);}return result; // 返回最终结果
}

③ 按位与运算

/** 不带模数* 快速幂运算* @param {number} a- 基数* @param {number} b- 指数* @returns {number} 计算结果 (a ^ b)*
function quick2 (a, b) {let ans = 1while(b) { // 当指数存在的时候// 如果指数是奇数,则要先拉出来一个底数乘到最终结果上,其余步骤和偶数一样操作// 如果指数是偶数,则要底数平方,指数除以2(如果是使用按位与运算,则使用 "b >>= 1")b/2if(b & 1) ans *= aa *= ab >>= 1 // b右移一位}return ans
}
console.log(quick2(2, 8)) // 256

使用示例

快速幂运算可以用于很多应用场景,包括计算大数的幂、加密算法、以及任何需要快速计算大数时。

示例代码

const MOD = 10 ** 9 + 7; // 定义模数console.log(modExp(2, 10, MOD)); // 输出: 1024
console.log(modExp(5, 3, MOD));  // 输出: 125
console.log(modExp(3, 7, MOD));  // 输出: 2187
console.log(modExp(10, 9, MOD)); // 输出: 1000000000

复杂度分析

  • 时间复杂度: ( O(log e) ) — 每次操作将指数减半。
  • 空间复杂度: ( O(1) ) — 仅使用常量级额外空间。

小结论

快速幂运算是一个非常实用且高效的算法,广泛应用于计算大数的幂以及各种算法中。了解并实现该算法可以显著提高程序运行效率,特别是在处理与模数运算相关的问题时。


相关文章:

快速幂运算

快速幂运算 一、快速幂运算快速幂运算(Exponentiation by Squaring)基本思想算法实现(②③为非递归)① 递归运算② 普通 除模运算(不带 **模数** 与 带 **模数**)③ 按位与运算 使用示例示例代码 复杂度分析…...

vue @import引入CSS scoped无效 造成全局样式污染

引入css文件导致全局样式污染 1.写在单组件的style里面css样式&#xff0c;如果标签内不加scoped可能会影响其他组件的样式 <style lang"scss" scoped> </style> 2.通过import引入的外部css文件&#xff0c;这种引入方式是全局的&#xff0c;也会影响其…...

基于Flask-Login简单登录和权限控制实践

1. 关于Flask-Login Flask-Login 是一个为python Flask Web框架设计的扩展,用于管理用户会话(用户登录状态)。它提供了简单的接口来处理用户登录、注销、记住用户等功能,同时确保用户会话的安全性。以下是 Flask-Login 的一些关键特性和功能: 1.1. 主要功能 用户会话管理…...

文件流---------获取文件的内容到控制台

总流程&#xff1a;先创建一个文本文件------->里面写入一些内容&#xff08;纯字母和字母加文字&#xff09;-----------> 然后通过输入流获取文件里面的内容&#xff0c;两种方式。 1.第一种&#xff0c;获取单个的字符 &#xff0c;先创建文件 &#xff0c;java.txt…...

idea 2024 build菜单不见了

Q如题 idea 2024 新版UI添加build和recompile菜单 A如图&#xff0c;右键顶部栏之后&#xff0c;点击Add to Main Toolbar菜单&#xff0c;在里面就能找到Build菜单&#xff0c;添加接口。 Recompile菜单的话在Customize Toolbar中搜索添加才行。...

深入理解计算机操作系统(持续更新中...)

文章目录 一、计算机系统漫游1.1信息就是位上下文 一、计算机系统漫游 1.1信息就是位上下文 源程序实际上就是一个由值0和1组成的位&#xff08;又称为比特&#xff09;&#xff0c;八个位被组织成一组&#xff0c;称为字节。每个字节表示程序中的某些文本字符 大部分现代计…...

[dp8_子数组] 乘积为正数的最长子数组长度 | 等差数列划分 | 最长湍流子数组

目录 1.乘积为正数的最长子数组长度 2.等差数列划分 3.最长湍流子数组 写代码做到&#xff0c;只用维护好自己的一小步 1.乘积为正数的最长子数组长度 链接&#xff1a;1567. 乘积为正数的最长子数组长度 给你一个整数数组 nums &#xff0c;请你求出乘积为正数的最长子数…...

量子机器学习(Quantum Machine Learning, QML)在优化测试组合

量子机器学习(Quantum Machine Learning, QML)在优化测试组合选择中展现出显著潜力,通过量子计算的并行性和量子态叠加特性,可高效解决传统方法难以处理的组合爆炸问题。以下是其技术实现路径、优势及落地案例: 一、QML优化测试组合的核心原理 1. 量子并行性加速搜索 经典…...

Go语言Slice切片底层

Go语言&#xff08;Golang&#xff09;中切片&#xff08;slice&#xff09;的相关知识、包括切片与数组的关系、底层结构、扩容机制、以及切片在函数传递、截取、增删元素、拷贝等操作中的特性。并给出了相关代码示例和一道面试题。关键要点包括&#xff1a; 数组特性&#xf…...

导入 Excel 批量替换文件夹名称

文件夹重命名的需求是多种多样的&#xff0c;前面我们介绍过按照规则修改文件夹名称的方法。但是在某些场景下&#xff0c;这个方法可能是不适用的&#xff0c;比如我们修改文件夹的规则是多种多样的&#xff0c;是无规律的。那我们应该怎么做呢&#xff1f;今天我们就给大家介…...

数据库或表数据迁移(使用Navicat迁移MySQL数据库表数据)

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 数据库或表数据迁移&#xff08;使用Navicat…...

Matlab Add Legend To Graph-图例添加到图

Add Legeng To Graph: Matlab的legend&#xff08;&#xff09;函数-图例添加到图 将图例添加到图 ,图例是标记绘制在图上的数据序列的有用方法。 下列示例说明如何创建图例并进行一些常见修改&#xff0c;例如更改位置、设置字体大小以及添加标题。您还可以创建具有多列的图…...

【Linux】what is pam?PAM模块学习笔记

文章目录 1. pam模块简介2. pam验证的工作流程3. pam模块配置文件3.1 配置文件的格式3.1.1 验证类别type3.1.2 验证的控制标识 control flag3.1.3 pam模块 4. login的PAM验证机制流程5. 补充&#xff1a;其他pam相关文件6. 参考内容 1. pam模块简介 PAM: Pluggable Authentica…...

5.1 GitHub订阅监控系统实战:FastAPI+SQLAlchemy高效架构设计与核心源码揭秘

GitHub Sentinel Agent 分析报告功能设计与实现 关键词:订阅管理 API 设计、GitHub API 集成、SQLAlchemy ORM、JWT 认证、单元测试框架 1. 订阅管理功能架构设计 订阅管理模块采用分层架构设计,通过 FastAPI 构建 RESTful 接口,结合 SQLAlchemy ORM 实现数据持久化: #me…...

【BEPU V1物理】BEPUphysics v1 入门指南 汉化笔记#1

BEPUphysics v1 入门指南 前言下载获取库工程1.创建物理模拟环境2.添加物理实体3.与物理系统交互4.发射物体5.构建环境6.事件处理7. 进阶学习 前言 本文档记录完成 BEPUphysics 物理引擎的基础设置。 文档链接:https://github.com/bepu/bepuphysics1/blob/master/Documentatio…...

方法加事务在多线程中注意事项

方法加事务在多线程中注意事项 redission分布式锁释放异常问题 https://www.jianshu.com/p/055ae798547a https://blog.csdn.net/cheng__yu/article/details/122625649 虽然文章 https://blog.csdn.net/cheng__yu/article/details/122625649 和 redission锁是没关系的&#…...

开源 2D 横版跳跃游戏 SuperTux

官网 https://www.supertux.org/ 正文 在游戏的世界里&#xff0c;开源游戏以其独特的魅力吸引着众多玩家和开发者。今天要介绍的 SuperTux&#xff0c;便是一款备受瞩目的开源 2D 横版跳跃游戏&#xff0c;风格类似经典的超级马里奥系列。 2024 年&#xff0c;SuperTux 开发团…...

基于HASM模型的高精度建模matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 本课题主要使用HASM进行高精度建模&#xff0c;主要对HASM模型进行介绍以及在实际中如何进行简化实现的。 2.测试软件版本以及运行结果展示 MATLAB2022A版本运行…...

C++多线程编程时的伪共享问题及其定位和解决

一、引言 在多线程编程和共享内存系统中&#xff0c;为了提高程序性能&#xff0c;常常需要对共享数据进行处理。然而&#xff0c;在并发环境下&#xff0c;一种名为“伪共享&#xff08;False Sharing&#xff09;”的问题可能会悄然出现&#xff0c;它虽然不像传统的多线程同…...

高并发短信系统设计:基于SharingJDBC的分库分表、大数据同步与实时计算方案

高并发短信系统设计&#xff1a;基于SharingJDBC的分库分表、大数据同步与实时计算方案 一、概述 在当今互联网应用中&#xff0c;短信服务是极为重要的一环。面对每天发送2000万条短信的需求&#xff0c;我们需要一个能够处理海量数据&#xff08;一年下来达到数千万亿级别&…...

【HTML】html文件

HTML文件全解析&#xff1a;搭建网页的基石 在互联网的广袤世界里&#xff0c;每一个绚丽多彩、功能各异的网页背后&#xff0c;都离不开HTML文件的默默支撑。HTML&#xff0c;即超文本标记语言&#xff08;HyperText Markup Language&#xff09;&#xff0c;作为网页创建的基…...

5.11 GitHub API调试五大高频坑:从JSON异常到异步阻塞的实战避坑指南

GitHub API调试五大高频坑:从JSON异常到异步阻塞的实战避坑指南 关键词:GitHub API 调试、JSON 解析异常、提示工程优化、异步任务阻塞、数据清洗策略 5.5 测试与调试:调试常见问题 问题1:GitHub API 调用异常 现象: requests.exceptions.HTTPError: 403 Client Error…...

协程的原生挂起与恢复机制

目录 &#x1f50d; 一、从开发者视角看协程挂起与恢复 &#x1f9e0; 二、协程挂起和恢复的机制原理&#xff1a;核心关键词 ✅ suspend 函数 ≠ 普通函数 ✅ Continuation&#xff08;协程的控制器&#xff09; &#x1f527; 三、编译器做了什么&#xff1f;&#xff0…...

机器学习中的数学(PartⅡ)——线性代数:2.2矩阵

概述 本节内容也相对简单&#xff0c;首先介绍了矩阵的定义&#xff0c;矩阵的表示方法&#xff1b;然后介绍了矩阵的加法和乘法&#xff0c;与标量的乘法&#xff0c;以及一些矩阵相关算数运算的性质&#xff0c;包括满足结合律、交换律&#xff1b;矩阵的逆和转置&#xff1…...

泉涌未来:科技与生态的共生诗篇-济南

故事背景 故事发生在中国山东济南的未来城市环境&#xff0c;这里不再是单纯的自然景观与现代建筑的堆砌&#xff0c;而是科技与生态深度融合的奇妙世界。泉水&#xff0c;这一济南的灵魂元素&#xff0c;在未来科技的赋能下&#xff0c;成为连接城市各个角落的纽带。量子态泉水…...

用AI生成系统架构图

DeepSeek+Drawio+SVG绘制架构图-找到一种真正可行实用的方法和思路 1、使用DeepSeek生成SVG文件,导入drawio工具的方法 🔥 问题根源分析 错误现象: • 导入时报错包含 data:image/SVG;base64 和 %20 等 URL 编码字符 • 代码被错误转换为 Base64 格式(适用于网页嵌入,但…...

网络基础1

目录 初识协议 协议分层 软件分层的好处 OSI七层模型 TCP/IP 五层(或四层)模型 再谈协议 为什么要有 TCP/IP 协议&#xff1f; TCP/IP 协议与操作系统的关系 所以究竟什么是协议&#xff1f; 网络传输基本流程 认识 MAC 地址 局域网(以太网为例)通信原理 报文的传…...

免费且好用的PDF水印添加工具

软件介绍 今天要给大家推荐一款超实用的PDF添加水印工具&#xff0c;它能够满足用户给PDF文件添加水印的需求&#xff0c;而且完全免费。 这款PDF添加水印的软件有着简洁的界面&#xff0c;操作简便&#xff0c;无需安装&#xff0c;解压后即可使用。 在使用前&#xff0c;先…...

C++Primer对象移动

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

互联网三高-数据库高并发之分库分表ShardingJDBC

1 ShardingJDBC介绍 1.1 常见概念术语 ① 数据节点Node&#xff1a;数据分片的最小单元&#xff0c;由数据源名称和数据表组成 如&#xff1a;ds0.product_order_0 ② 真实表&#xff1a;再分片的数据库中真实存在的物理表 如&#xff1a;product_order_0 ③ 逻辑表&#xff1a…...

七、自动化概念篇

自动化测试概念 自动化测试是把以人为驱动的测试行为转化为机器执行的一种过程。通常&#xff0c;在设计了测试用例并通过评审之后&#xff0c;由测试人员根据测试用例中描述的过程一步步执行测试&#xff0c;得到实际结果与期望结果的比较。在此过程中&#xff0c;为了节省人…...

python操作mongodb

1、安装包 pyMongo是MongoDB官方推荐的Python驱动程序&#xff0c;它提供了访问MongoDB数据库所需的接口。安装PyMongo非常简单&#xff0c;可以通过pip包管理工具来安装最新版本&#xff1a; pip install pymongo 安装完成后&#xff0c;我们可以使用以下Python代码来检查是否…...

IS-IS中特殊字段——OL过载

文章目录 OL 过载位 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Datacom专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2025年04月13日20点12分 OL 过载位 路由过载 使用 IS-IS 的过载标记来标识过载状态 对设备设置过载标记后&#xff…...

行星际激波在日球层中的传播:Propagation of Interplanetary Shocks in the Heliosphere (第二部分)

行星际激波在日球层中的传播&#xff1a;Propagation of Interplanetary Shocks in the Heliosphere &#xff08;第一部分&#xff09;-CSDN博客 Propagation of Interplanetary Shocks in the Heliosphere [ Chapter 3 ] [PDF: arXiv] 本文保留原文及参考文献&#xff0c;参…...

紫光同创FPGA实现HSSTLP光口视频点对点传输,基于Aurora 8b/10b编解码架构,提供6套PDS工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐我已有的所有工程源码总目录----方便你快速找到自己喜欢的项目紫光同创FPGA相关方案推荐我这里已有的 GT 高速接口解决方案Xilinx系列FPGA实现GTP光口视频传输方案推荐Xilinx系列FPGA实现GTX光口视频传输方案推荐Xilinx系列FPGA实…...

正则表达式使用知识(日常翻阅)

正则表达式使用 一、字符匹配 1. 普通字符 描述&#xff1a;直接匹配字符本身。示例&#xff1a; abc 匹配字符串中的 “abc”。Hello 匹配字符串中的 “Hello”。 2. 特殊字符 .&#xff08;点号&#xff09;&#xff1a; 描述&#xff1a;匹配任意单个字符&#xff08;…...

CSS padding(填充)学习笔记

CSS 中的 padding&#xff08;填充&#xff09;是一个非常重要的属性&#xff0c;它用于定义元素边框与元素内容之间的空间&#xff0c;即上下左右的内边距。合理使用 padding 可以让页面布局更加美观、清晰。以下是对 CSS padding 的详细学习笔记。 一、padding 的作用 padd…...

Python中的字符串、列表、字典和集合详解

Python是一门强大的编程语言&#xff0c;其内置的数据结构丰富多样。其中&#xff0c;字符串、列表、字典和集合是最常用的数据类型。本文将对它们的区别、用法和使用场景进行详细介绍&#xff0c;帮助大家更好地理解和应用这些数据结构。 1. 字符串&#xff08;String&#xf…...

【CUDA编程】CUDA Warp 与 Warp-Python 对比文档

相关文档: Nvidia-Warp GitHub&#xff1a;nvidia/warp CUDA Warp 和 Warp-Python 库 的对比与统一文档&#xff0c;涵盖两者的核心概念、区别、使用场景及示例&#xff1a; 1. CUDA Warp&#xff08;硬件/编程模型概念&#xff09; 1.1 定义与核心概念 定义&#xff1a; C…...

中厂算法岗面试总结

时间&#xff1a;2025.4.10 地点&#xff1a;上市的电子有限公司 面试流程&#xff1a; 1.由负责人讲解公司文化 2&#xff0c;由技术人员讲解公司的技术岗位&#xff0c;还有成果 3.带领参观各个工作位置&#xff0c;还有场所 4.中午吃饭 5.面试题&#xff0c;闭卷考试…...

Losson 4 NFS(network file system(网络文件系统))

网络文件系统&#xff1a;在互联网中共享服务器中文件资源。 使用nfs服务需要安装:nfs-utils 以及 rpcbind nfs-utils : 提供nfs服务的程序 rpcbind &#xff1a;管理nfs所有进程端口号的程序 nfs的部署 1.客户端和服务端都安装nfs-utils和rpcbind #安装nfs的软件rpcbind和…...

自动化运行后BeautifulReport内容为空

一、问题描述 自动化程序运行后发现运行目录下生成的html报告文件内容为空&#xff0c;没有运行结果。 二、测试环境 操作系统&#xff1a;Windows 11 家庭版BeautifulReport&#xff1a;0.1.3Python&#xff1a;3.11.9Appium-Python-Client&#xff1a;5.0.0Appium Server:2.…...

CTF-WEB排行榜制作

CTF-WEB排行榜制作 项目需求&#xff1a; 现在14道题对应有14个flag&#xff0c;我需要使用dockerfile搭建一个简单的&#xff0c;能够实现验证这些题目对应的flag来计分的简单网站&#xff08;要求页面比较精美&#xff09; 前十题设置为10分 11-14题设置为20分 1. flag{5a3…...

架构生命周期(高软57)

系列文章目录 架构生命周期 文章目录 系列文章目录前言一、软件架构是什么&#xff1f;二、软件架构的内容三、软件设计阶段四、构件总结 前言 本节讲明架构设计的架构生命周期概念。 一、软件架构是什么&#xff1f; 二、软件架构的内容 三、软件设计阶段 四、构件 总结 就…...

STM32单片机定时器的输入捕获和输出比较

目录 一、定时器的输入捕获 1、工作原理 2、示例代码 二、定时器的输出比较 1、工作原理 2、示例代码 三、总结 在STM32单片机中&#xff0c;定时器是一个非常重要的外设&#xff0c;广泛应用于时间管理、事件计时、波形生成等多种场景。其中输入捕获和输出比较是两个基…...

计算机组成原理-系统总线

1. 系统总线的定义 系统总线是计算机系统中各功能部件&#xff08;CPU、存储器、I/O设备等&#xff09;之间传递信息的公共通路&#xff0c;遵循统一的电气规范和时序协议&#xff0c;是计算机硬件互联的基础。 核心作用&#xff1a;实现数据、地址和控制信号的传输&#xff…...

【android bluetooth 框架分析 02】【Module详解 3】【HciHal 模块介绍】

1. 背景 我们在 gd_shim_module 介绍章节中&#xff0c;看到 我们将 HciHal 模块加入到了 modules 中。 modules.add<hal::HciHal>();在 ModuleRegistry::Start 函数中我们对 加入的所有 module 挨个初始化。 而在该函数中启动一个 module 都要执行那下面几步&#xff…...

Git 远程仓库

Git 入门笔记 远程仓库 Git 远程仓库 Git 远程仓库是一个托管在网络服务器上的代码仓库&#xff0c;它是团队协作开发的核心。 通过远程仓库&#xff0c;开发者可以共享代码、同步更新&#xff0c;实现分布式协作。 SSH 密钥 SSH 密钥可以让你在使用 Git 时安全地连接远程…...

209.长度最小的子数组- 力扣(LeetCode)

题目&#xff1a; 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0 。 示例 1&#xff1a;…...

符号右移“ >>= “ 与 无符号右移“ >>>= “ 的区别

符号右移" >> " 与 无符号右移" >>> " 的区别 一、符号右移" >> " 与 无符号右移" >>> " 的区别1. 符号右移&#xff08;>>&#xff09;与无符号右移&#xff08;>>>&#xff09;的区别…...