【STUACM-算法入门-快速幂】https://www.bilibili.com/video/BV1Hi4y1L7qB?p=2&vd_source=e583d26dc0028b3e6ea220aadf5bc7fe
想先把a的b次方算出来再对p取模是不可能的，因为肯定超出long long 范围。
需要知道：(x*y)mod p = (x mod p)*(y mod p) mod p
这样考虑：
long long sum = 1;
for(int i = 0;i< b;i ++)
sum = (sum * a) % p;这样会超时，因为b可能很大，需要引入快速幂算法
快速幂的方法很多，这里介绍一种
举一个具体的例子，比如计算2的15次方mod9
15 的二进制是 1111
2^15 = 2^(8)*2^(4)*2^(2)*2(1) = 2^(2^3) * 2^(2^2)*2(2^1)*2(2^0)，像这样把
因为b的二进制位数最多31位，所以只需要算出a^(2^1)mod q——a^(2^32)mod q次方即可(这里mod q是由于之间保存a的高次幂会超出范围，根据模运算的性质保存取模之后的数）
我们不妨建立一个数组num,num[i] 保存着 a^(2^i) mod p的值 ，然后看看b的二进制有哪些位是1，依次判断最后计算时要取num数组中的哪些项。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num[34];//num[i] recorded a^(2^i) mod p的值
void func(ll a,ll p){//打表ll sum = 1;num[0] = a % p;for(int i = 1;i < 32;i ++){num[i] = (num[i - 1] * num[i - 1]) % p;}
}
ll calculate(ll b,ll p){ll ans = 1;ll temp,i = 0;while(b){temp = b & 1;if(temp){ans = (ans * num[i]) % p;}b = b >> 1;i ++;}return ans;
}
int main(){ll a,b,p;cin >> a >> b >> p;func(a,p);printf("%lld^%lld mod %lld=%lld",a,b,p,calculate(b,p));return 0;
}
//2^15 15 = b1111 2^15 = 2^(8)*2^(4)*2^(2)*2(1)
// = 2^(2^3) * 2^(2^2)*2(2^1)*2(2^0)
