【算法设计-分治思想】快速幂与龟速乘
文章目录
- 1. 快速幂
- 2. 龟速乘
- 3. 快速幂取模
- 4. 龟速乘取模
- 5. 快速幂取模优化
1. 快速幂
算法原理:
- 计算 311:
- 311 = (35)2 x 3
- 35 = (32)2 x 3
- 32 = 3 x 3
- 仅需计算 3 次,而非 11 次
- 计算 310:
- 310 = (35)2
- 35 = (32)2 x 3
- 32 = 3 x 3
- 仅需计算 3 次,而非 10 次
算法思路:
- 若指数是偶数,则将底数平方,指数除以 2。
- 若指数是奇数,则将底数平方,指数除以 2,再乘上底数。
算法代码:
typedef unsigned long long uLL;// 快速幂 a^b
uLL power (uLL a, uLL b){uLL r = 1;while (b != 0){if (b & 1) // (b % 2 == 1)r = r * a;b = b >> 1; // (b = b / 2)a = a * a;}return r;
}
举例:
- 初始值:a = 3,b = 11
- 第 1 轮:(11 % 2 == 1)r=1x3=3,b=5,a=32=9
- 第 2 轮:(5 % 2 == 1)r=3x32=33=27,b=2,a=(32)2=34=81
- 第 3 轮:(2 % 2 == 0)r 不变,b=1,a=(34)2=38
- 第 4 轮:(1 % 2 == 1)r=33x38=311,b=0,a=(38)2=316
- 得到 r = 33x38 = 311
2. 龟速乘
算法原理:将其中一个乘数分解成 2 的幂次相加。
12 x a = 23 x a + 21 x a
算法代码:
typedef unsigned long long uLL;// 龟速乘 a*b
uLL mul (uLL a, uLL b){uLL r = 0;while (b != 0){if (b & 1) // (b % 2 == 1)r = r + a;b = b >> 1; // (b = b / 2)a = a + a;}return r;
}
3. 快速幂取模
初等数论中有如下公式:
(a × b) % m = ((a % m) × (b % m)) % m
推广:
(a × b × c…) % m = ((a % m) × (b % m) × (c % m) × … ) % m
(ab) % m = (a × a × a…) % m = ((a % m) × (a % m) × (a % m) × … ) % m
算法代码:
typedef unsigned long long uLL;// 快速幂取模 (a^b) % p
uLL powerMod (uLL a, uLL b, uLL p){uLL r = 1;while (b != 0){if (b & 1) // (b % 2 == 1)r = (r * a) % p;b = b >> 1; // (b = b / 2)a = (a * a) % p;}return r;
}
4. 龟速乘取模
算法原理:(a × b) % m = ((a % m) × (b % m)) % m
算法代码:
// 龟速乘取模 (a*b) % p
uLL mulMod (uLL a, uLL b, uLL p){uLL r = 0;while (b != 0){if (b & 1) // (b % 2 == 1)r = (r + a) % p;b = b >> 1; // (b = b / 2)a = (a + a) % p;}return r;
}
5. 快速幂取模优化
算法原理:注意到快速幂取模算法中的相乘操作可能会超出数据范围,因此可以将相乘操作转化为龟速乘取模。
原理依然是此公式:(a × b) % m = ((a % m) × (b % m)) % m,其中((a % m) × (b % m))即为龟速乘取模。
算法思路:快速幂 + 龟速乘结合。
// 快速幂取模防止爆炸 (a^b) % p
uLL powerModBig (uLL a, uLL b, uLL p){uLL r = 1;while (b != 0){if (b & 1) // (b % 2 == 1)r = mulMod(a, b, p) % p;b = b >> 1; // (b = b / 2)a = mulMod(a, a, p) % p;}return r;
}
相关文章:
【算法设计-分治思想】快速幂与龟速乘
文章目录1. 快速幂2. 龟速乘3. 快速幂取模4. 龟速乘取模5. 快速幂取模优化1. 快速幂 算法原理: 计算 311: 311 (35)2 x 335 (32)2 x 332 3 x 3仅需计算 3 次,而非 11 次 计算 310: 310 (35)235 (32)2 x 332 3 x 3仅需计算…...
Kafka(十一) 如何保证数据的不重复和不丢失
数据不丢失 1)从生产端:acks -1,(ack应答机制)从生产端到节点端,当所有isr集合里的节点备份完毕后返回成功; 2)从节点端:每个partition至少需要一个isr节点࿰…...
解决树莓派 bullseye (11) 系统无法通过 xrdp 远程连接的问题
我手上有一台树莓派 4B,使用官方镜像烧录器烧录老版本操作系统 buster (10) 时可以正常通过 Windows 远程桌面连接上,但换成最新的 bullseye (11) 系统后却无法正常连接远程桌面。 问题复现: 使用官方镜像烧录器烧录,配置用户名为…...
微信公众号历史作品定向采集
最近有遇到微信公众号历史作品采集的需求,这里做一下记录, 登录自己注册好的的微信公众号后台进入创作界面,点击右上角的引用: 弹出如下界面: 选择查找公众号文章,输入要查找的公众号: 回车: 同时就可以打开F12开始抓包,选择公众号点击进入: appmsg?action=li…...
Vue学习笔记(3)
3.1 计算属性和监视属性 3.1.1 计算属性 计算属性是一种计算值的方式,可以根据其他属性的值来动态地计算新的属性值。计算属性可以缓存计算结果,当依赖的属性发生改变时,才会重新计算。在Vue中,可以使用computed选项来定义计算属…...
Marshmallow 库
文章目录Marshmallow 库介绍使用序列化反序列化参数介绍schema参数fields 参数钩子函数内置验证器Meta 属性Marshmallow 库 介绍 marshmallow是一个用来将复杂的orm对象与python原生数据类型之间相互转换的库,简而言之,就是实现object -> dict&#…...
【BN层的作用】论文阅读 | How Does Batch Normalization Help Optimization?
前言:15年Google提出Batch Normalization,成为深度学习最成功的设计之一,18年MIT团队将原论文中提出的BN层的作用进行了一一反驳,重新揭示BN层的意义 2015年Google团队论文:【here】 2018年MIT团队论文:【h…...
re.sub()用法的详细介绍
一、前言 在字符串数据处理的过程中,正则表达式是我们经常使用到的,python中使用的则是re模块。下面会通过实际案例介绍 re.sub() 的详细用法,该函数主要用于替换字符串中的匹配项。 二、函数原型 首先从源代码来看一下该函数原型…...
【Python数据挖掘入门】2.2文本分析-中文分词(jieba库cut方法/自定义词典load_userdict/语料库分词)
中文分词就是将一个汉字序列切分成一个一个单独的词。例如: 另外还有停用词的概念,停用词是指在数据处理时,需要过滤掉的某些字或词。 一、jieba库 安装过程见:https://blog.csdn.net/momomuabc/article/details/128198306 ji…...
Meta利用视觉信息来优化3D音频模型,未来将用于AR/VR
我们知道,Meta为了给AR眼镜打造智能助手,专门开发了第一人称视觉模型和数据集。与此同时,该公司也在探索一种将视觉和语音融合的AI感知方案。相比于单纯的语音助手,同时结合视觉和声音数据来感知环境,可进一步增强智能…...
openlayers加载离线地图并实现深色地图
问题背景 我们自己一直使用的openlayergeoserver自己发布的地图,使用的是矢量地图。但是由于政府地图大都使用为天地图,所以需要将geoserver的矢量地图更改为天地图,并且依旧是搭配openlayers来使用。 解决步骤 一:加载离线地图&a…...
socket,tcp,http三者之间的区别和原理
目录 一、OSI模型也称七层网络模型 1、TCP/IP连接 1.1三次握手与四次挥手的简单理解:(面试重点) 1.2面试考题:如果已经建立了连接,但是客户端突然出现故障了怎么办? 1.3 socket、tcp、http三者之间有什…...
红日(vulnstack)1 内网渗透ATTCK实战
环境准备 靶机链接:百度网盘 请输入提取码 提取码:sx22 攻击机系统:kali linux 2022.03 网络配置: win7配置: kali配置: kali 192.168.1.108 192.168.111.129 桥接一块,自定义网卡4 win7 1…...
ik 分词器怎么调用缓存的词库
IK 分词器是一个基于 Java 实现的中文分词器,它支持在分词时调用缓存的词库。 要使用 IK 分词器调用缓存的词库,你需要完成以下步骤: 创建 IK 分词器实例 首先,你需要创建一个 IK 分词器的实例。可以通过以下代码创建一个 IK 分…...
ROS1/2机器人操作系统与时间Time的不解之缘
时间对于机器人操作系统非常重要。所有机器人类的编程中所涉及的变量如果需要在网络中传输都需要这个数据结构的时间戳。宏观上,ROS1、ROS2各版本都有官方支持的时间节点。ROS时钟--支持时间倒计时小工具效果如下:如果要部署机器人操作系统,R…...
华为OD机试真题2022(JAVA)
华为机试题库已换 →→→ 华为OD机试2023(JAVA) 以下题目为旧版题库,供大家课外消遣 基础题: 序号题目分值1查找众数及中位数1002出错的或电路1003连续字母长度1004分班1005计算面积1006最远足迹1007判断一组不等式是否满足约束…...
【3】MyBatis+Spring+SpringMVC+SSM整合一套通关
三、SpringMVC 1、SpringMVC简介 1.1、什么是MVC MVC是一种软件架构的思想,将软件按照模型、视图、控制器来划分 M:Model,模型层,指工程中的JavaBean,作用是处理数据 JavaBean分为两类: 一类称为实体…...
20道前端高频面试题(附答案)
ES6新特性 1.ES6引入来严格模式变量必须声明后在使用函数的参数不能有同名属性, 否则报错不能使用with语句 (说实话我基本没用过)不能对只读属性赋值, 否则报错不能使用前缀0表示八进制数,否则报错 (说实话我基本没用过)不能删除不可删除的数据, 否则报错不能删除变量delete p…...
android EditText设置后缀
有两种实现方案。 方案一:是自己写一个TextWatcher。 方案二:是重写TextView的getOffsetForPosition方法,返回一个计算好的offset。 我在工作时,使用的是方案一。在离职之后,我还是对这个问题耿耿于怀,所以…...
prometheus+cadvisor监控docker
官方解释 cAdvisor(ContainerAdvisor)为容器用户提供了对其运行容器的资源使用和性能特性的了解。它是一个正在运行的守护程序,用于收集、聚合、处理和导出有关正在运行的容器的信息。具体来说,它为每个容器保存资源隔离参数、历史…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
