题目描述
给你三个整数 b,p,k，求 \(b^p\) mod k。
输入格式
输入只有一行三个整数，分别代表 b,p,k。
输出格式
输出一行一个字符串 b^p mod k=s，其中b,p,k分别为题目给定的值，s为运算结果。
数据规模与约定
对于100%的数据，保证0 \(\leq\) b,p \(\leq\) \(2^{31}\)，1 \(\leq\) k \(\leq\) \(2^{31}\) 。
思路
快速幂的模板题，没有什么好说的。有两个细节需要注意:
1)a%2==1与a&1==1是等价的。
2)取模的运算不会干涉乘法运算。
3)根据费马小定理，如果k是一个质数，我们可以计算\(b^{p mod(k-1)}\)来加速算法过程。
代码如下:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll b,p,k;
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod "<<k<<"="<<binpow(b%k,p,k)%k<<endl;
return 0;
}