给定 n n n组 a i , b i , p i a_i,b_i,p_i ai?,bi?,pi?，对于每组数据，求出 a i b i ? m o d ? p i a_i^{b^i}~mod~p_i aibi??mod?pi? 的值。
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
用来解决快速的求解
a
k
?
m
o
d
a^k~mod
ak?mod
p
p
p的结果
时间复杂度为
O
(
l
o
g
k
)
O(logk)
O(logk)
预处理出来这些值：
a
2
0
?
m
o
d
?
p
a^{2^0}~mod~p
a20?mod?p
a
2
1
?
m
o
d
?
p
a^{2^1}~mod~p
a21?mod?p
a
2
2
?
m
o
d
?
p
a^{2^2}~mod~p
a22?mod?p
.
.
.
...
...
a
2
l
o
g
k
?
m
o
d
?
p
a^{2^{logk}}~mod~p
a2logk?mod?p
大概是logk个
则
a
k
a^k
ak可以表示为前面分解的这些数的某些数的乘积
则
k
k
k可以表示为
2
2
2的若干次幂的和
（利用k的二进制表示）
a
k
=
a
2
x
1
a
2
x
2
.
.
.
a
2
x
t
=
a
2
x
1
+
2
x
2
+
.
.
.
+
2
x
t
a^k =a^{2^{x_1}}a^{2^{x_2}}...a^{2^{x_t}} =a^{2^{x_1}+2^{x_2}+...+2^{x_t}}
ak=a2x1?a2x2?...a2xt?=a2x1?+2x2?+...+2xt?
如何求
a
x
a^x
ax？
a
1
?
=
?
a
a^1~=~a
a1?=?a
a
2
1
?
=
?
(
a
1
)
2
a^{2^1}~=~(a^{1})^2
a21?=?(a1)2
a
2
2
?
=
?
(
a
2
1
)
2
a^{2^2}~=~(a^{2^1})^2
a22?=?(a21)2
.
.
.
...
...
a
2
l
o
g
k
?
=
?
(
a
2
l
o
g
k
?
1
)
2
a^{2^{logk}}~=~(a^{2^{logk}-1})^2
a2logk?=?(a2logk?1)2
也就是说，后一个数都是前一个数的平方
也就是经过k次迭代，就可以把这些数分解出来了
其实就是看k的二进制表示里面，哪些位是1，把1对应的这些位对应的数乘起来就可以了
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int k, int p){
LL res = 1 % p;
while(k){
if(k & 1) res = res * a % p; //如果最后一位是1，乘上a^2^a%p
a = a * (LL)a % p; //a向后迭代，继续平方
k >>= 1; //把k的最后以为删掉
}
return res;
}
int main(){
int n, a, b, p;
cin >> n;
while(n--){
scanf("%d%d%d", &a, &b, &p);
printf("%lld\n", qmi(a, b, p));
}
return 0;
}
作者：为梦而生
链接：https://www.acwing.com/solution/content/220897/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。