P1226 【模板】快速幂||取余运算 C++
2021/4/24 14:25:32
本文主要是介绍P1226 【模板】快速幂||取余运算 C++,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
日期:2021-04-24
作者:19届WY
标签:快速幂,同余运算
题目描述
同余运算的主要性质
解题:
- 利用同余运算的性质,可以每次将p进行二分取余,若p为偶数,则xp=(x2)p/2,若p为奇数,则xp=x*(x2)p/2。
- (考虑p>0的情况)每次将p/2,若p为奇数,则xp=x*(x2)p/2,中前面那个单独的x也要取余之后再放进s中,若p为偶数则直接计算x2再取余,这里不用再与s进行计算,因为最后一步总会得到p=1,结果都会进入s中
- (考虑p=0的情况)最后输出的时候要再取一次余,举例:若b=5,p=0,k=1,因为p=0所以不会进入循环,所以s没有经过运算保持为1,但明显结果应该为0,所以要再取一次余
- 注意一下b,p的值会被改变,所以存一下开始输入的值
#include<iostream> using namespace std; int main(){ long long b,p,k,i,a,c; cin >> b >> p >> k; a=b; c= p; long long s=1; while(p>0){ if(p%2 == 1){ s = s * b % k; } b = b * b % k; p = p / 2; } cout<<a<<"^"<<c<<" "<<"mod"<<" "<<k<<"="<<s%k; }
辣鸡解法:
一开始想到的是直接递归,一直二分递归,没有理解快速幂的思想,60分,超时了
#include<iostream> using namespace std; long long mod(long long a,long long b, long long c); int main(){ long long b,p,k,i; cin >> b >> p >> k; long long s = mod(b,p,k); cout<<b<<"^"<<p<<" "<<"mod"<<" "<<k<<"="<<s; } long long mod(long long a,long long b, long long c){ int ans; if(b == 1) return a % c; return (mod(a, b/2, c) % c)* (mod(a, b - b/2, c) % c) % c; }
这篇关于P1226 【模板】快速幂||取余运算 C++的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享