当前位置: 首页 > 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....

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...