我是靠谱客的博主 动人冷风,这篇文章主要介绍快速幂取模 代码如下,如有错误,欢迎指正,现在分享给大家,希望可以做个参考。

问题:

求 a的 b 次方对 p 取模的值。

对于较小的数,我们可以用暴力解法,用循环b次的方法来实现,算法复杂度为O(N),但是对于b比较大的情况,那么这种算法时间复杂度就很大了,因此引出了快速幂的定义:

实例分析:

例如我们要求2^7,首先我们可以将7的2进表示出来

7 = 111;

那么有:

2^1 = 2;

2^2 = 4;

2^4 = 16;

要求2^7,只需要将以上三个数相乘即可,从而简化运算,时间复杂度也变成了O(logN)

 代码如下,如有错误,欢迎指正

#include <iostream>
#include <cstdio>
using namespace std;
long long a,b,p;
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
long long ans = 1%p;
long long res = a,l
= b;
for(;l;l>>=1,res = (res*res)%p)
{
if(l&1)
{
ans = (ans*res)%p;
}
}
printf("%lldn",ans);
return 0;
}

 

最后

以上就是动人冷风最近收集整理的关于快速幂取模 代码如下,如有错误,欢迎指正的全部内容,更多相关快速幂取模 代码如下内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(52)

评论列表共有 0 条评论

立即
投稿
返回
顶部