【模板】快速幂||取余运算
程序员文章站
2024-01-14 14:26:10
...
快速幂
最后一个测试点:
输入:
1 0 1
输出:
1^0 mod 1=0
版本1
#include<cstdio>
typedef long long LL;
int main(){
LL b,p,k;
LL ans=1;
scanf("%lld%lld%lld",&b,&p,&k);
printf("%lld^%lld mod %lld=",b,p,k);
while(p>0){
if(p&1) ans = ans*b % k;
b = b*b % k;
p >>= 1;
}
printf("%lld",ans%p);
return 0;
}
版本2
#include<cstdio>
#include<iostream>
using namespace std;
long long bp(long long a, long long b, long long m){
long long ans = 1;
while(b>0){
if(b&1){
ans = ans*a % m;
}
a = a*a % m;
b >>= 1;
}
return ans%m;
}
int main(){
long long b,p,k;
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod "<<k<<"="<<bp(b,p,k)<<endl;
return 0;
}
版本3
#include<cstdio>
#include<iostream>
using namespace std;
long long binaryPow(long long a, long long b, long long m){
if(b==0) return 1%m;
if(b&1) return a*binaryPow(a, b-1, m)%m;
else{
long long mul = binaryPow(a,b/2,m);
return mul*mul%m;
}
}
int main(){
long long b,p,k;
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod "<<k<<"="<<binaryPow(b,p,k)<<endl;
return 0;
}
上一篇: (取余运算)快速幂
下一篇: 关于里氏替换原则(LSP)