题目链接：https://www.acwing.com/activity/content/problem/content/323/1/
89. a^b
求 aa 的 bb 次方对 pp 取模的值。
输入格式
三个整数 a,b,pa,b,p ,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
0≤a,b,p≤1090≤a,b,p≤109
输入样例：
3 2 7
输出样例：
2解题思路：首先暴力的写法是乘一个a然后就对p取一次余，但是这样会超时。基于二进制的思想，我们可以将b写成一个二进制数，这样我们每对b右移以为就让a乘以自己，并且当b是奇数的时候就将答案乘上一个a同时对p取余数。这样时间复杂度就是logn。这样就不会超时了。AC代码：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
inline int qm(int a, int b, int p) {
LL res = 1;
LL tmp = a;
while(b) {
if(b & 1) res = (res * tmp) % p;
tmp = (LL)tmp * tmp % p;
b >>= 1;
}
return res;
}
int main(void) {
// freopen("in.txt", "r", stdin);
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
if(b == 0) printf("%d\n", 1 % p);
else printf("%d\n", qm(a, b, p));
return 0;
}
转载于:https://www.cnblogs.com/phaLQ/p/11460570.html
相关资源：JAVA上百实例源码以及开源项目
