当前位置: 首页 > 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;互联网金融平台也成为中国消费金融业务最重要的参与方之一&#…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

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

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

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...