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-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享