AcWing 89. a^b
原题链接
简单
作者:
殇ベ_11
,
2021-02-07 09:19:23
,
所有人可见
,
阅读 311
题目描述
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数,表示a^b mod p的值。
数据范围
0≤a,b≤109
1≤p≤
样例
输入样例:
3 2 7
输出样例:
2
算法1
(快速幂+取余运算)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
long long fastPower(long long base, long long power,int k) {
long long result = 1;
while (power > 0) {
if (power & 1) {
result = result * base % k;
}
power >>= 1;
base = (base * base) % k;
}
return result;
}
int main()
{
int a, b, k;
scanf("%d%d%d", &a, &b, &k);
if(b==0&&k==1){
cout<<"0";
return 0;
}
else if(b==0&&k!=1){
cout<<1;
return 0;
}
printf("%d",fastPower(a, b, k));
return 0;
}
好厉害啊