89. a^b
求 aa 的 bb 次方对 pp 取模的值。
输入格式
三个整数 a,b,pa,b,p ,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
0≤a,b≤1090≤a,b≤109
1≤p≤1091≤p≤109
输入样例：
3 2 7
输出样例：
2
a,b,p=[int(x)for x in input().split()]
'''
如何计算a^b ab是两个大整数
5^100000
1.迭代需要计算10^5次
2.快速幂
100000的 二进制为00000001 10000110 10100000
所以，5^100000 = 5^(2**6) * 5^(2**8) * 5^(2**10) * 5^(2**11) * 5^(2**16) * 5^(2**17)
其中，5*(2**x)可以在迭代中维护，所以只需要计算6次
也就是说，对于一个32位整数a,b来说，使用快速幂计算a^b次方最多计算31次
'''
k=0
r=1%p # 防止 a^0 % 1的情况
for i in range(32):
if b & (1<<i):
r=r*a % p
a=(a*a)%p
print(r)