题目描述
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数,表示a^b mod p的值。
数据范围
0≤a,b,p≤109
样例
输入样例:
3 2 7
输出样例:
2
注意:输入的a,b,p要用long long
算法1
(快速幂算法一 | 递归写法) $O(log(b))$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll binaryPow(ll a, ll b, ll p)
{
if(b==0) return 1%p;
if(b%2==1) return a*binaryPow(a,b-1,p)%p;
else{
ll mul = binaryPow(a,b/2,p);
return mul*mul%p;
}
}
int main(){
ll a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
ll ans = binaryPow(a,b,p);
printf("%lld",ans);
return 0;
}
算法2
(快速幂二|迭代写法) $O(n^2)$
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int main(){
ll a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
ll ans=1;
if(b==0) ans = 1%p;
while(b>0)
{
if(b&1)
{
ans = ans*a%p;
}
a = a*a%p;
b >>= 1;
}
printf("%lld",ans);
return 0;
}