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

快速幂算法

快速幂算法

文章目录

一、简单介绍

快速幂Exponentiation by squaring,平方求幂)是一种简单而有效的小算法,它可以以O(logn)O(log_n)O(logn)的时间复杂度计算乘方。快速幂不仅本身非常常见,而且后续很多算法也都会用到快速幂。

二、计算7107^{10}710

​ 让我们先来思考一个问题:7的10次方,怎样算比较快?

​ 最朴素的想法,77=49,497=343,… 一步一步算,共进行了9次乘法。这样算无疑太慢了,尤其对计算机的CPU而言,每次运算只乘上一个个位数,无疑太屈才了。这时我们想到,也许可以拆分问题。

​ 我们换一个角度来引入快速幂。还是7的10次方,但这次,我们把10写成二进制的形式,也就是 1010。于是这个问题就变成了求7的二进制(1010)次幂。这样就只需要计算4次,相比于9次,大大提升了效率。

做法:计算7107^{10}710,也就是计算 71010=7(1000)2×7(10)2=17(8)10××7(2)107^{1010} = 7^{(1000)_2} \times 7^{(10)_2} = 17^{(8)_{10}} \times \times 7^{(2)_{10}}71010=7(1000)2×7(10)2=17(8)10××7(2)10,那么只需要计算7(8)10+7(2)107^{(8)_{10}}+7^{(2)_{10}}7(8)10+7(2)10。更一般化,只需要计算720,721,722,...,72n7^{2^{0}},7^{2^{1}},7^{2^{2}},...,7^{2^{n}}720,721,722,...,72n

三、一般化

1、计算ana^nan的快速方法:

(1)将nnn 转化成二进制形式,例如1011010

(2)转化后的形式为a(xkxk−1...x2x1x0)2=axk0...00×a0xk−1...00×a00...10×a00...01a^{(x_kx_{k-1}...x_2x_1x_0)_2} = a^{x_k0...00} \times a^{0x_{k-1}...00} \times a^{00...10} \times a^{00...01}a(xkxk1...x2x1x0)2=axk0...00×a0xk1...00×a00...10×a00...01.

(3) 需要计算的数值为a1,a2,a4,a8,....,a2na^{1},a^{2},a^{4},a^{8},....,a^{2^{n}}a1,a2,a4,a8,....,a2n.

2、时间复杂度分析:

一般求解 ana^nan 时,需要计算n次。但是使用快速幂算法之后,将nnn 表示成二进制只需要O(logn)O(log_n)O(logn) 位数字,只需要计算O(logn)O(log_n)O(logn)次。

四、代码

public static Long quickPow(Long a,Long n,Long p){//结果Long res = 1L;while (n != 0) {//判断 n 的二进制的最后一位是否为0if((n&1)!=0){//当n的二进制最后一位为1时,乘以当前的权重res = (res*a)%p;}//更新n,每次n向右移一位n = n >> 1;//更新每一位的权重a = (a*a)%p;}return res;
}

五、参考资料

[1] 基础算法—快速幂详解

[2] 快速幂算法

幂算法](https://blog.csdn.net/HouGOD/article/details/123847315)

相关文章:

快速幂算法

快速幂算法 文章目录快速幂算法一、简单介绍二、计算7107^{10}710三、一般化1、计算ana^nan的快速方法:2、时间复杂度分析:四、代码五、参考资料一、简单介绍 ​ 快速幂(Exponentiation by squaring,平方求幂)是一种简…...

Hudi:问题总结(2)Flink-1.13.1消费kafka并插入hudi

问题一:java.lang.ClassNotFoundException: com.google.protobuf.MessageOrBuilder) 解决:字面意思,没找到类,将protobuf-java-3.2.0-jar包放到fink/lib/下 如果报commons-cli相关的错,就将commons-cli-1.4.jar放到f…...

Application工具方法

//注册这个接口registerActivityLifecycleCallbacks(activityLifecycleCallbacks);}Overridepublic void onTerminate() {//注销这个接口。unregisterActivityLifecycleCallbacks(activityLifecycleCallbacks);super.onTerminate();}public static List<Activity> activi…...

电脑游戏怎么录屏?其实很简单,只需要简单3步

电脑游戏一直是游戏爱好者最热衷的游戏之一。但是&#xff0c;有时候我们想分享我们在游戏中的精彩时刻&#xff0c;或者记录我们的游戏过程以便后续观看和学习。在这种情况下&#xff0c;录屏就成了必不可少的工具。但是&#xff0c;许多人可能不知道电脑游戏怎么录屏。在本文…...

【设计模式】go语言中的 [函数选项,单例,工厂,责任链] 常用的设计模式

文章目录前言一、函数选项模式二、单例模式三、工厂模式四、责任链模式前言 宿舍每人 温度38℃&#xff0b; 大寄 设计模式很重要&#xff0c;设计模式其实就是为了解决某一类问题而形成的代码写法&#xff0c;设计模式很多&#xff0c;但是并不是每个都很常用&#xff0c;我们…...

2017系统分析师案例分析真题背记内容

前言 以下内容仅为个人根据当年系分案例真题问题整理的偏需要记背的考点答案&#xff0c;方便个人背诵和记忆使用。方便文字转语音&#xff0c;所以内容全为纯文字内容&#xff0c;以下内容仅供参考。 背记内容 微服务 微服务中应该包含的内容有&#xff1a;资源、对资源的…...

C++和C的区别

答&#xff1a;从宏观角度和微观角度分析微观角度&#xff1a;函数原型有区别&#xff0c;在c中&#xff0c;函数原型有参数和没有参数是不同的&#xff0c;并且允许申明多个同名的函数&#xff0c;只要他们的参数列表不同或者返回值不同即可&#xff0c;但是在c语言中不能。C引…...

【React教程】一、React简介

一、React简介 React是一个用于构建用户界面的JavaScript库&#xff0c;它是Facebook的内部项目&#xff0c;用来架设Instagram的网站,并于2013年5月开源。React主要用于构建Ul&#xff0c;很多人认为React 是 MVC 中的 V&#xff08;视图&#xff09;。由于拥有较高的性能&…...

运动蓝牙耳机什么牌子好,比较好的运动蓝牙耳机推荐

现在市面上的运动蓝牙耳机越来越多&#xff0c;在选择耳机的时候应该如何入手呢&#xff1f;最重要的是需要按照自己的需求来选择&#xff0c;但在耳机的配置上不能忽视的是耳机的防水等级&#xff0c;运动耳机对防水等级的要求更高&#xff0c;这样能够更好地防御汗水浸湿耳机…...

[深入理解SSD系列 闪存实战2.1] NAND FLASH特性串烧 | 不了解闪存特性,你能用好闪存产品吗?

前言 为了利用好闪存, 发挥闪存的优势, 以达到更好的性能和使用寿命, 那自然要求了解闪存特性。 闪存作为一种相对较新的存储介质, 有很多特别的特性。 一.闪存的特性 凡是采用Flash Memory的存储设备,可以统称为闪存存储。我们经常谈的固态硬盘(SSD),可以由volatile/…...

DJI ROS dji_sdk 源码分析|整体框架

DJI ROS dji_sdk 源码分析|整体框架launch文件CMakeLists.txtcpp文件main.cppOSDK 是一个用于开发无人机应用程序的开发工具包&#xff0c;基于OSDK 开发的应用程序能够运行在机载计算机上&#xff08;如Manifold 2&#xff09;&#xff0c;开发者通过调用OSDK 中指定的接口能够…...

HT32合泰单片机开发环境搭建和配置教程

HT32合泰(Holtek)单片机开发环境搭建安装教程 前言 最近在准备合泰杯的比赛&#xff0c;在看合泰官方的PPT和数据手册学习&#xff0c;顺便做个合泰单片机的开发环境搭建教程。 合泰杯比赛发放的开发板是ESK32-30501&#xff0c;用的单片机是HT32F52352。 合泰杯官网地址&a…...

动态内存分配之伙伴算法

伙伴算法 伙伴算法是一种在计算机内存管理中使用的算法&#xff0c;用于分配和释放内存。它是一种基于二叉树的动态内存分配算法&#xff0c;可以高效地分配和合并内存块。伙伴算法是一种按照固定大小分配内存的算法&#xff0c;例如&#xff0c;每个内存块的大小为2的n次幂&a…...

CGAL 根据扫描线方向和角度对法向量进行重定向

目录一、算法原理1、主要函数二、代码实现一、算法原理 最小生成树对法向量定向的结果在具有许多尖锐特征和遮挡的机载点云数据中结果并不理想。scanline_orient_normals()是专门用于具有扫描线特性的点云法向量重定向的替代方法。它充分利用了某些激光雷达扫描器的LAS特性&…...

一个C#开发的开源的快速启动工具

更多开源项目请查看&#xff1a;一个专注推荐.Net开源项目的榜单 平常计算机安装软件比较多、或者工作涉及的文件比较多&#xff0c;很多人都会直接放在桌面&#xff0c;一方面不安全&#xff0c;还不容易查找&#xff0c;这时候我们往往&#xff0c;都会放在其他硬盘内&#x…...

Paddle项目调试记录

PaddlePaddle是百度公司提出的深度学习框架。近年来深度学习在很多机器学习领域都有着非常出色的表现&#xff0c;在图像识别、语音识别、自然语言处理、机器人、网络广告投放、医学自动诊断和金融等领域有着广泛应用。面对繁多的应用场景&#xff0c;深度学习框架有助于建模者…...

3月11日,30秒知全网,精选7个热点

///微盟集团宣布接入百度文心一言 据介绍&#xff0c;微盟SaaS产品和数字营销服务将与文心一言的技术能力实现深度融合&#xff0c;通过AIGC技术&#xff0c;深化微盟在营销AI创意内容生产、智能营销、智能客服、智能经营等方面的布局 ///T3出行与华为云深化业务合作 双方将在…...

C win32基础学习(四)

上一篇我们已经介绍了关于窗口处理函数的知识。本篇我们说一下注册窗口类&#xff0c;创建窗口和显示窗口的内容。 前文 窗口创建过程 定义WinMain函数 定义窗口处理函数(自定义&#xff0c;处理消息) 注册窗口类&#xff08;向操作系统写入一些数据&#xff09; 创建窗口&…...

Java 日期时间API(Java 8及以上)

Java 8及以上版本提供了新的日期时间API&#xff0c;其中包括了LocalDate、LocalTime、LocalDateTime、ZonedDateTime、Duration、Period等类&#xff0c;这些类提供了更加丰富和灵活的日期时间操作方法。 LocalDate LocalDate类表示一个本地日期&#xff0c;不包含时间和时区…...

DHCP的配置

实验目的熟悉DHCP的应用场景掌握DHCP的配置方法实验拓扑DHCP的配置如图15-2所示: 图15-2:DHCP的配置 实验步骤配置IP地址<Huawei>system-view Enter system view, return user view with Ctrl+Z....

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...