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

洛谷 P1226:【模板】快速幂

【题目来源】
https://www.luogu.com.cn/problem/P1226

【题目描述】
给你三个整数 a,b,p,求 a^b mod p。

【输入格式】
输入只有一行三个整数,分别代表 a,b,p。

【输出格式】
输出一行一个字符串 a^b mod p=s,其中 a,b,p 分别为题目给定的值,s 为运算结果。

【输入样例】
2 10 9

【输出样例】
2^10 mod 9=7

【说明/提示】
样例解释:2^10 =1024,1024 mod 9=7。
数据规模与约定:对于 100% 的数据,保证 0≤a,b<2^31,a+b>0,2≤p<2^31。

【算法分析】
● 快速幂,又称二进制取幂,是一个以 O(logn) 的时间复杂度计算 a^{n} 的
小技巧,而暴力的计算需要 O(n) 的时间复杂度。

● 快速幂的原理?
答:快速幂的原理为“将求幂的任务按照指数 n 的
二进制表示分割成更小的任务”。例如:
3^{7}=3^{111_{(2)}}=3^{2^2} \times 3^{2^1} \times 3^{2^0}=3^4 \times 3^2\times 3^1
3^{11}=3^{1011_{(2)}}=3^{2^3} \times 3^{2^1} \times 3^{2^0}=3^8 \times 3^2\times 3^1
因为 n\left \lfloor log_2n \right \rfloor+1 个二进制位,因此当知道了 a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}} 后,我们只需计算 O(log n) 次乘法就可以计算出 a^n


● 快速幂经典代码

#include <bits/stdc++.h>
using namespace std;typedef long long LL;int fastPow(LL a,LL n) {LL ans=1;while(n){if(n & 1) ans=ans*a;n>>=1;a=a*a;}return ans;
}int main() {int a,n;cin>>a>>n;cout<<fastPow(a,n)<<endl;
}/*
in:6 8
out:1679616
*/

● 带取模的快速幂代码
计算过程中,为了
防止溢出,需要进行“取模”运算,其运算规则如下:
(a+b)%p=(a%p+b%p)%p
(a-b)%p=(a%p-b%p)%p
(a*b)%p=(a%p*b%p)%p


【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;int fastPow(LL a,LL b,LL p) {LL ans=1;while(b){if(b & 1) ans=ans*a%p;b>>=1;a=a*a%p;}return ans%p;
}int main() {int a,b,p;cin>>a>>b>>p;cout<<a<<"^"<<b<<" mod "<<p<<"="<<fastPow(a,b,p)%p;
}/*
in:2 10 9
out:2^10 mod 9=7
*/






【参考文献】
https://www.cnblogs.com/littlehb/p/15588930.html
https://oi-wiki.org/math/binary-exponentiation/


 

相关文章:

洛谷 P1226:【模板】快速幂

【题目来源】https://www.luogu.com.cn/problem/P1226【题目描述】 给你三个整数 a&#xff0c;b&#xff0c;p&#xff0c;求 a^b mod p。【输入格式】 输入只有一行三个整数&#xff0c;分别代表 a&#xff0c;b&#xff0c;p。【输出格式】 输出一行一个字符串 a^b mod ps&a…...

nginx常规操作

Linux下查找Nginx配置文件位置 1、查看Nginx进程 ps -aux | grep nginx 圈出的就是Nginx的二进制文件 2、测试Nginx配置文件 /usr/sbin/nginx -t 可以看到nginx配置文件位置 3、nginx的使用(启动、重启、关闭) 首先利用配置文件启动nginx。 nginx -c /usr/local/nginx/conf…...

Docker镜像不能访问

Get "https://registry-1.docker.io/v2/": dial tcp 192.168.10.194:443: connect: connection refused Idea推送镜像至Harbor私服&#xff0c;报以上错误&#xff0c;Docker镜像地址不能访问&#xff0c;更新Harbor服务器Docker镜像地址&#xff0c;重启Docker服务…...

TCP simultaneous open测试

源代码 /*************************************************************************> File Name: common.h> Author: hsz> Brief:> Created Time: 2024年10月23日 星期三 09时47分51秒**********************************************************************…...

Spring 配置文件动态读取pom.xml中的属性

需求&#xff1a; 配置文件中的 spring.profiles.active${env}需要打包时动态绑定。 一、方案&#xff1a; 在pom.xml文件中配置启用占位符替换 <profiles><!-- 本地开发 --><profile><id>dev</id><properties><env>dev</env>…...

Konva 组,层级

代码&#xff1a; <template><div class"rect"><div class"header"> <!-- <el-button type"primary" click"show">展示</el-button>--> <!-- <el-button type"success&quo…...

vue图片加载失败的图片

1.vue图片加载失败的图片 这个问题发生在测试环境和开发本地&#xff0c;线上环境是可以的&#xff0c;测试环境估计被第三方屏蔽了 2.图片有&#xff0c;却加载不出来 <template v-slot:imageUrlsSlots"{ row }"><div class"flexRow rowCenter"&…...

终止,半成收入来自海外,收入可持续性被质疑

芬尼科技终止原因如下&#xff1a;芬尼科技4年期间经历了两次IPO失败&#xff0c;公司半成收入来自海外&#xff0c;然而公司泳池收入面临欧洲地区冲突冲击及德国新节能措施影响。交易所质疑其收入是否具有可持续性。 作者&#xff1a;Eric 来源&#xff1a;IPO魔女 9月25日&a…...

日常记录,使用springboot,vue2,easyexcel使实现字段的匹配导入

目前的需求是数据库字段固定&#xff0c;而excel的字段不固定&#xff0c;需要实现excel导入到一个数据库内。 首先是前端的字段匹配&#xff0c;显示数据库字段和表头字段 读取表头字段&#xff1a; 我这里实现的是监听器导入&#xff0c;需要新建一个listen类。 读Excel …...

Unable to open nested entry ‘********.jar‘ 问题解决

今天把现网版本的task的jar拖回来然后用7-zip打开拖了一个jar进去替换mysql-connector-java-5.1.47.jar 为 mysql-connector-java-5.1.27.jar 启动微服务的时候就报错下面的 Exception in thread "main" java.lang.IllegalStateException: Failed to get nested ar…...

反编译华为-研究功耗联网监控日志

摘要 待机功耗中联网目前已知的盲点&#xff1a;App自己都不知道的push类型的被动联网、app下载场景所需时长、组播联网、路由器打醒AP。 竞品 策略 华为 灭屏使用handler定时检测&#xff08;若灭屏30分钟内则周期1分钟&#xff0c;否则为2分钟&#xff09;&#xff0c;检…...

线程池——Java

一、前言 在字符串常量池中&#xff0c;字符串常量在java程序运行之前就已经创建好了&#xff0c;等程序运行起来后&#xff0c;就可以直接从常量池中拿到字符串并加载到内存中&#xff0c;这样的设计就省下了字符串的构造与销毁的内存开销。 二、优势 操作系统由内核与应用程…...

java 17天 TreeSet以及Collections

SortedSet TreeSet Collections 所有单值集合 1 SortedSet 特点&#xff1a;有序 唯一 实现类&#xff1a;TreeSet 利用TreeSet特有的对数据进行升序&#xff0c;再放到ArryList进行for下标倒序打印&#xff0c;或者利用自身的pollLast&#xff08;&#xff09;取出最后元…...

JavaScript 第27章:构建工具与自动化

在现代JavaScript开发中&#xff0c;构建工具、代码转换工具、代码质量和代码格式化工具对于提高开发效率、保持代码整洁以及确保代码质量有着至关重要的作用。下面将分别介绍Webpack、Babel、ESLint和Prettier的配置与使用&#xff0c;并给出一些示例。 1. 构建工具&#xff…...

Android原生ROM出现WIFI显示网络连接受限,网络无法连接的问题

Android原生ROM出现WIFI显示网络连接受限,网络无法连接的问题 最近手里一台乐视的手机root后, 连接wifi时一直提示网络连接受限,wifi图标显示叹号. 但是不影响正常的网络访问. 解决办法: adb shell settings delete global captive_portal_modeadb shell settings put globa…...

如何实现网页上的闪烁效果

在网页上实现闪烁效果通常可以通过CSS或者JavaScript来完成。有两种方法&#xff1a;一种是使用纯CSS&#xff0c;另一种是结合JavaScript来创建更复杂的闪烁效果。 方法一&#xff1a;使用纯CSS CSS中可以使用animation属性来创建简单的动画效果&#xff0c;包括闪烁效果。这…...

事件总线—Event Bus 使用及讲解

一、工作原理 事件总线&#xff0c;主要用来实现非父子组件之间的传值。 它的工作原理&#xff1a;通过new Vue()再创建一个新的 Vue 实例对象bus&#xff0c;将这个新的实例对象作为桥梁&#xff0c;来实现两个组件之间的传值。 二、工作步骤 1、创建事件总线 bus 我们可以…...

信息安全工程师(67)网络流量清洗技术与应用

前言 网络流量清洗技术是现代网络安全领域中的一项关键技术&#xff0c;它主要用于过滤和清理网络流量中的恶意部分&#xff0c;确保正常的网络通信。 一、网络流量清洗技术的定义与原理 网络流量清洗技术&#xff0c;也称为流量清理&#xff08;Traffic Scrubbing&#xff09;…...

【项目】论坛系统测试

文章目录 一、项目介绍二、测试环境三、测试用例3.1 论坛系统功能测试用例3.2 论坛系统非功能测试用例 四、测试计划1. 手工测试1.1 注册页面1.2 登陆页面1.3 主页面&#xff08;列表页&#xff09; 2. 自动化测试2.1 添加对应的依赖2.2 Utils类&#xff08;公有类&#xff09;…...

XJ02、消费金融|消费金融业务模式中的主要主体

根据所持有牌照类型的不同&#xff0c;消费金融服务供给方主要分为商业银行、汽车金融公司、消费金融公司和小贷公司&#xff0c;不同类型机构定位不同、提供消费金融服务与产品类型也各不相同。此外&#xff0c;互联网金融平台也成为中国消费金融业务最重要的参与方之一&#…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

HTML 列表、表格、表单

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

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

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

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

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...