90. 64位整数乘法
求 aa 乘 bb 对 pp 取模的值。
输入格式
第一行输入整数aa，第二行输入整数bb，第三行输入整数pp。
输出格式
输出一个整数，表示a*b mod p的值。
数据范围
1≤a,b,p≤10181≤a,b,p≤1018
输入样例：
3
4
5
输出样例：
2
a=int(input())
b=int(input())
p=int(input())
'''
如何计算a*b? ab是两个超大整数，10^18级别
使用快速幂思想
快速幂可以快速计算 a*a*a*...*a 其中a有10^9项
而，axb=a+a+a+...+a 这里乘法变成了加法，同样可以使用快速幂解决
例如：647 * 100000
100000 二进制为 11000011010100000
所以 647 * 100000 = 647*(2**6 + 2**8 + 2**10 + 2**11 + 2**16 + 2**17)
迭代过程中维护 647*(2**x) 这样只需要计算6次
a
a*2
'''
r=0
while b:
if b&1: r= (r+a)%p
b>>=1
a=a*2 %p
print(r)