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

AcWing89. a^b

题目

a a a b b b 次方对 p p p 取模的值。

输入格式

三个整数 a , b , p , a,b,p, a,b,p, 在同一行用空格隔开。

输出格式

输出一个整数,表示 a^b mod p 的值。

数据范围

0 ≤ a , b ≤ 1 0 9 0≤a,b≤10^9 0a,b109

1 ≤ p ≤ 1 0 9 1≤p≤10^9 1p109

输入样例

3 2 7

输出样例

2

思路

快速幂

任何一个整数都可以唯一表示为若干指数不重复的 2 的次幂的和。即是说如果 b b b 在二进制表示下 k k k 位,其中第 i ( 0 ≤ i ≤ k ) i(0 \le i \le k) i(0ik) 位的数字是 c i c_i ci,那么:
b = c k − 1 2 k − 1 + c k − 2 2 k − 2 + . . . + c 0 2 0 b = c_{k-1}2^{k-1} + c_{k-2}2^{k-2} + ... + c_0 2^0 b=ck12k1+ck22k2+...+c020
于是
a b = a c k − 1 × 2 k − 1 ∗ a c k − 2 × 2 k − 2 ∗ . . . ∗ a c 0 × 2 0 a ^b = a^{c_{k-1}\times2^{k-1}} * a^{c_{k-2} \times 2^{k-2}} * ... * a^{c_0 \times 2^0} ab=ack1×2k1ack2×2k2...ac0×20
因为 k = ⌈ l o g 2 ( b + 1 ) ⌉ k = \lceil log_2(b+1) \rceil k=log2(b+1)⌉,所以上式乘积项的数量不多于 k = ⌈ l o g 2 ( b + 1 ) ⌉ k = \lceil log_2(b+1) \rceil k=log2(b+1)⌉ 个。又因为:
a 2 i = ( a 2 i − 1 ) 2 a^{2^i} = (a^{2^{i-1}})^2 a2i=(a2i1)2
所以可以通过 k k k 次递归求出每个乘积项,当 c i = 1 c_i = 1 ci=1 时,将该乘积项累积到答案中。KaTeX parse error: Expected 'EOF', got '&' at position 3: b &̲ 1 运算可以取出 b b b 在二进制表示下的最低位,而 b > > 1 b >> 1 b>>1 运算可以舍去最低位,在递推过程中将二者集合,就可以遍历 b b b 在二进制表示下的所有数位 c i c_i ci

整个算法的时间复杂度为 O ( l o g 2 b ) O(log_2b) O(log2b)

代码

#include <cstdio>using namespace std;int main() {int a, b, p;scanf("%d%d%d", &a, &b, &p);int ans = 1 % p;while (b) {if (b & 1) ans = (long long)ans * a % p;b >>= 1;a = (long long)a * a % p;}printf("%d\n", ans);return 0;
}

注意

在 C++ 语言中,两个数值执行算术运算时,以参与运算的最高数值类型为基准,与保存结果的变量类型无关。换言之,虽然两个 32 位整数的乘积可能超过 int 类型的表示范围,但是 CPU 只会用 1 个 32 位寄存器保存结果,造成越界现象。因此,必须把其中一个数强制转换成 64 位整数类型 long long 参与运算,从而得到正确的结果。最终对 p p p 取模以后,执行赋值操作时,该结果会被隐式转换成 int 存回 ans 中。

相关文章:

AcWing89. a^b

题目 求 a a a 的 b b b 次方对 p p p 取模的值。 输入格式 三个整数 a , b , p , a,b,p, a,b,p, 在同一行用空格隔开。 输出格式 输出一个整数&#xff0c;表示 a^b mod p 的值。 数据范围 0 ≤ a , b ≤ 1 0 9 0≤a,b≤10^9 0≤a,b≤109 1 ≤ p ≤ 1 0 9 1≤p≤10^…...

【推荐系统】推荐算法:冷启动-召回-粗排-精排-重排 解读

【推荐系统】推荐算法&#xff1a;冷启动-召回-粗排-精排-重排 解读 文章目录 【推荐系统】推荐算法&#xff1a;冷启动-召回-粗排-精排-重排 解读1. 介绍2. 冷启动2.1 用户冷启动2.1.1 利用用户注册信息冷启动2.1.2 好物推荐冷启动2.1.3 问题启发式冷启动2.1.4 社交冷启动2.1.…...

NB-IOT的粮库挡粮门异动监测装置

一种基于NBIOT的粮库挡粮门异动监测装置,包括若干个NBIOT开门监测装置,物联网后台管理系统,NBIOT低功耗广域网络和用户访问终端;各个NBIOT开门监测装置通过NBIOT低功耗广域网络与物联网后台管理系统连接,物联网后台管理系统与用户访问终端连接.NBIOT开门监测装置能够对粮库挡粮…...

六、【图像去水印】

文章目录 裁剪法移动复制法内容识别去水印色阶法去水印消失点法去水印反相混合法 裁剪法 处于边缘的水印&#xff0c;通过裁剪去除&#xff0c;如下图&#xff1a; 移动复制法 移动复制法适用于水印的背景这部分区域比较相似的情况下使用&#xff0c;如下图先使用矩形选区选中…...

电子电器架构 —— 车载网关初入门(二)

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 PS:小细节,本文字数5000+,详细描述了网关在车载框架中的具体性能设置。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 没有人关注你。也无需有人关注你。你必须承认自己的价值,你不能站在他…...

AT32固件库外设使用,ArduinoAPI接口移植,模块化

目录 一、ArduinoAPI移植一、通用定时器使用1.计时1.2.ETR外部时钟计数4.ArduinoAPI - timer 三、ADC1.ADC初始化&#xff08;非DMA&#xff09;2.ADC_DMA 规则通道扫描 六、USB HID IAP1.准备好Bootloader和app2.配置好时钟&#xff0c;一定要打开USB3.将生成的时钟配置复制到…...

【Postgres】Postgres常用命令

文章目录 1、导出数据库某张表2、导入某张表到数据库3、查看数据库占用磁盘页数情况4、查看数据库大小5、查看数据表大小6、查看索引大小7、对数据库中表索引按照大小排序8、对数据库中表按照大小排序9、回收空间&#xff08;建议先回收指定表&#xff09;10、设置主键自增序列…...

pthread 读写锁使用详解

pthread 读写锁使用 读写锁&#xff1a;提供了一种高效的机制来控制对共享资源的访问。允许多个线程同时读取共享资源&#xff0c;但只允许一个线程独占地写入访问。适用于读取远远超过写入的场景下&#xff0c;因为写入操作需要独占地访问资源&#xff0c;可能会影响读取操作…...

MySQL扩展语句

if not exists xiaobu&#xff1a;xiaobu这个表不存在&#xff0c;才会创建 zerofill&#xff1a;自动填充位置 1 0001 primary key&#xff1a;当前表的主键&#xff0c;主键只能有一个&#xff0c;而且唯一&#xff0c;而且不能为空 auto_increment&#xff1a;表示该字段…...

阿里云号码认证服务(一键登录)在连接wifi的情况下部分机型下存在的问题

手机型号&#xff1a; vivo S16 存在的现象&#xff1a; 安装手机卡(联通卡)&#xff0c;且连接wifi的情况下&#xff0c;APP登录唤起阿里云一键登录服务大概有90%左右必超时(按照阿里云一键登录官方文档设置的超时时间为5秒)。 解决方案&#xff1a; 1、APP端增加超时判断&…...

电脑屏幕监控软件,能够帮助企业完成哪些事情?

电脑屏幕监控软件是一种能够监控和管理员工在电脑上的操作行为的软件。分为两种监控方式&#xff1a;实时监控和屏幕记录监控。实时监控是对电脑屏幕进行实时录像&#xff0c;屏幕记录监控则是以屏幕快照的形式保存下来&#xff0c;供使用者随时查看。电脑屏幕监控软件&#xf…...

java--方法的其他形式

1.方法定义时&#xff1a;需要按照方法解决的实际业务需求&#xff0c;来设计合理的方法形式解决问题。 1.注意事项 ①如果方法不需要返回数据&#xff0c;返回值类型必须申明成void(无返回值申明)&#xff0c;此时方法内部不可以使用return返回数据。 ②方法如果不需要接收数…...

IDEA配置类、方法注释模板

一、打开 IDEA 的 Settings&#xff0c;点击 Editor–>File and Code Templates&#xff0c;点击右边 File 选项卡下面的 Class&#xff0c;在其中添加图中红框内的内容&#xff1a; /** * author li-kun * date ${YEAR}年${MONTH}月${DAY}日 ${TIME} */当你创建一个新的类…...

PowerDesigner 16数据库(mysql)逆向生成pdm

1、配置数据源 2、测试数据源 but~~~~没成功&#xff0c;shift...

Spring Cloud 之Feign

前言 Feign是一个声明式的Web服务客户端&#xff0c;使得编写HTTP客户端变得更简单。在Java程序中&#xff0c;只需要在方法前加上FeignClient注解&#xff0c;Feign就会自动创建一个HTTP客户端&#xff0c;向指定的URL发送请求。 核心概念 1、注解&#xff1a;在服务接口方…...

通用开源自动化测试框架 - Robot Framework

一、什么是 Robot Framework&#xff1f; 1. Robot Framework 的历史由来 Robot Framework是一种通用的自动化测试框架&#xff0c;最早由Pekka Klrck在2005年开发&#xff0c;并由Nokia Networks作为内部工具使用。后来&#xff0c;该项目以开源形式发布&#xff0c;并得到了…...

css position属性与js滚动

“视口”就是浏览器窗口中实际显示文档内容的区域&#xff0c;不包含浏览器的“外框”&#xff0c;如菜单、工具条和标签。文档则是指整个网页。 1 css 的position static 正常定位&#xff0c;是元素position属性的默认值&#xff0c;元素遵循常规流。 relative 相对定位&…...

python内置模块hashlib对于字符串的加密解密加盐

hash是一类算法而hashlib模块是Python的一个内置模块&#xff0c;主要功能是使用对应的hash算法&#xff0c;加密二进制内容解密二进制内容 常见的hash算法有md5、sha1&#xff0c;sha256, sha512等 特点 1.内容敏感,那怕一个很小的字符发生改变都很明显 2.不可逆,不能逆向求值…...

获取客户端请求IP及IP所属城市

添加pom依赖 <dependency> <groupId>org.lionsoul</groupId> <artifactId>ip2region</artifactId> <version>2.6.5</version> </dependency> public class IpUtil { private…...

【洛谷 P1106】删数问题 题解(贪心+字符串)

删数问题 题目描述 键盘输入一个高精度的正整数 N N N&#xff08;不超过 250 250 250 位&#xff09;&#xff0c;去掉其中任意 k k k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 N N N 和 k k k&#xff0c;寻找一种方案使得剩下的数字组成…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

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

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