首页 > 极客资料 博客日记
洛谷P1226 【模板】快速幂
2024-08-07 10:00:05极客资料围观29次
本篇文章分享洛谷P1226 【模板】快速幂,对你有帮助的话记得收藏一下,看极客之家收获更多编程知识
1.快速幂模板
前置知识
一个数字n,它的二进制位数一定是log2n向下取整+1;
快速幂模板代码
这段代码实现了快速幂算法(Exponentiation by squaring),用来计算 ( an ) 的值,其中 ( a ) 和 ( n ) 都是整数。
int quickpow(int a, int n)
{
int res = 1; // 初始化结果为1,因为任何数的0次幂都是1
while (n) { // 当指数n不为0时,继续执行循环
if (n & 1) // 如果n的最低位为1(即n是奇数)
res = res * a; // 将当前底数a乘到结果中
a = a * a; // 将底数a平方,相当于底数翻倍,指数减半
n >>= 1; // 将指数n右移一位,相当于将指数减半
}
return res; // 返回计算结果
}
现在逐句解析每一行代码的作用:
-
int res = 1;
- 初始化变量
res
为1,这是最终结果的初始值。任何数的0次幂都是1。
- 初始化变量
-
while (n) {
- 进入一个循环,条件是当指数
n
不为0时继续执行。循环将持续执行直到n
变为0。
- 进入一个循环,条件是当指数
-
if (n & 1)
- 判断当前的指数
n
是否为奇数,使用位运算n & 1
来判断。如果n
的最低位(即最右边的二进制位)为1,则说明n
是奇数。
- 判断当前的指数
-
res = res * a;
- 如果
n
是奇数,则将当前的底数a
乘到结果res
中。这步实现了快速幂算法中的乘法操作。
- 如果
-
a = a * a;
- 然后将底数
a
自乘,即a
变成a^2
。这一步相当于将底数翻倍,对应于指数减半的操作。
- 然后将底数
-
n >>= 1;
- 将指数
n
右移一位,即n
变成n / 2
。这一步实现了快速幂算法中的指数减半操作。
- 将指数
-
循环回到第2步,直到
n
变为0,退出循环。 -
return res;
- 返回最终计算得到的结果
res
,即底数a
的指数n
次幂的值。
- 返回最终计算得到的结果
这段代码利用了快速幂算法的思想,通过迭代和位运算的方式,将指数的计算复杂度从 ( O(n) ) 优化到 ( O(log n) ),显著提高了计算效率。
快速幂算法的形象解释
快速幂算法的例题
【模板】快速幂
题目描述
给你三个整数 \(a,b,p\),求 \(a^b \bmod p\)。
输入格式
输入只有一行三个整数,分别代表 \(a,b,p\)。
输出格式
输出一行一个字符串 a^b mod p=s
,其中 \(a,b,p\) 分别为题目给定的值, \(s\) 为运算结果。
样例 #1
样例输入 #1
2 10 9
样例输出 #1
2^10 mod 9=7
提示
样例解释
\(2^{10} = 1024\),\(1024 \bmod 9 = 7\)。
数据规模与约定
对于 \(100\%\) 的数据,保证 \(0\le a,b < 2^{31}\),\(a+b>0\),\(2 \leq p \lt 2^{31}\)。
答案
这题直接套用快速幂算法的模板,只需要每一步我们加上取模运算即可,注意数据需要开long long类型
#include<iostream>
using namespace std;
long long quickpow(long long a, long long n,long long p)
{
long long res = 1;
while (n) {
if (n & 1) res = (res * a)%p;
a = (a * a)%p;
n >>= 1;
}
return res;
}
int main()
{
long long a, b, p;
cin >> a >> b >> p;
printf("%lld^%lld mod %lld=%lld", a, b, p, quickpow(a, b, p));
return 0;
}
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”