欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【模板】快速幂||取余运算

程序员文章站 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;
}