洛谷 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。
【算法分析】
● 快速幂,又称二进制取幂,是一个以 的时间复杂度计算
的小技巧,而暴力的计算需要
的时间复杂度。
● 快速幂的原理?
答:快速幂的原理为“将求幂的任务按照指数 的二进制表示分割成更小的任务”。例如:
因为 有
个二进制位,因此当知道了
后,我们只需计算
次乘法就可以计算出
。
● 快速幂经典代码
#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,b,p,求 a^b mod p。【输入格式】 输入只有一行三个整数,分别代表 a,b,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私服,报以上错误,Docker镜像地址不能访问,更新Harbor服务器Docker镜像地址,重启Docker服务…...

TCP simultaneous open测试
源代码 /*************************************************************************> File Name: common.h> Author: hsz> Brief:> Created Time: 2024年10月23日 星期三 09时47分51秒**********************************************************************…...
Spring 配置文件动态读取pom.xml中的属性
需求: 配置文件中的 spring.profiles.active${env}需要打包时动态绑定。 一、方案: 在pom.xml文件中配置启用占位符替换 <profiles><!-- 本地开发 --><profile><id>dev</id><properties><env>dev</env>…...

Konva 组,层级
代码: <template><div class"rect"><div class"header"> <!-- <el-button type"primary" click"show">展示</el-button>--> <!-- <el-button type"success&quo…...

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

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

日常记录,使用springboot,vue2,easyexcel使实现字段的匹配导入
目前的需求是数据库字段固定,而excel的字段不固定,需要实现excel导入到一个数据库内。 首先是前端的字段匹配,显示数据库字段和表头字段 读取表头字段: 我这里实现的是监听器导入,需要新建一个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…...

反编译华为-研究功耗联网监控日志
摘要 待机功耗中联网目前已知的盲点:App自己都不知道的push类型的被动联网、app下载场景所需时长、组播联网、路由器打醒AP。 竞品 策略 华为 灭屏使用handler定时检测(若灭屏30分钟内则周期1分钟,否则为2分钟),检…...
线程池——Java
一、前言 在字符串常量池中,字符串常量在java程序运行之前就已经创建好了,等程序运行起来后,就可以直接从常量池中拿到字符串并加载到内存中,这样的设计就省下了字符串的构造与销毁的内存开销。 二、优势 操作系统由内核与应用程…...
java 17天 TreeSet以及Collections
SortedSet TreeSet Collections 所有单值集合 1 SortedSet 特点:有序 唯一 实现类:TreeSet 利用TreeSet特有的对数据进行升序,再放到ArryList进行for下标倒序打印,或者利用自身的pollLast()取出最后元…...
JavaScript 第27章:构建工具与自动化
在现代JavaScript开发中,构建工具、代码转换工具、代码质量和代码格式化工具对于提高开发效率、保持代码整洁以及确保代码质量有着至关重要的作用。下面将分别介绍Webpack、Babel、ESLint和Prettier的配置与使用,并给出一些示例。 1. 构建工具ÿ…...
Android原生ROM出现WIFI显示网络连接受限,网络无法连接的问题
Android原生ROM出现WIFI显示网络连接受限,网络无法连接的问题 最近手里一台乐视的手机root后, 连接wifi时一直提示网络连接受限,wifi图标显示叹号. 但是不影响正常的网络访问. 解决办法: adb shell settings delete global captive_portal_modeadb shell settings put globa…...
如何实现网页上的闪烁效果
在网页上实现闪烁效果通常可以通过CSS或者JavaScript来完成。有两种方法:一种是使用纯CSS,另一种是结合JavaScript来创建更复杂的闪烁效果。 方法一:使用纯CSS CSS中可以使用animation属性来创建简单的动画效果,包括闪烁效果。这…...

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

信息安全工程师(67)网络流量清洗技术与应用
前言 网络流量清洗技术是现代网络安全领域中的一项关键技术,它主要用于过滤和清理网络流量中的恶意部分,确保正常的网络通信。 一、网络流量清洗技术的定义与原理 网络流量清洗技术,也称为流量清理(Traffic Scrubbing)…...

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

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

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...

k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...