初学快速幂，蒻蒻的发表一下感想

  1. 就是快速幂模板，首先要清楚a,b的范围为为（0,10^9）要用long long型，如果按照普通的一个一个去乘的话，肯定会爆范围，且时间复杂度为O(b),这时应该就用到了算法：快速幂O(logb)(基于二分的思想)
  2. 有一个公式为(ab)%mod=((a%mod)(b%mod))mod ，可以更好地理解快速幂，

证明：设 a = k1 * mod + q1 , b = k2 * mod + q2 a * b = (--------) * mod^2 + (------) * mod + q1 * q2 , 在除以 mod 前面就等于0,就只剩下q1 * q2, 两边在同时对mod取余，
（a * b）%mod = (q1 * q2)%mod a % mod = q1 , b % mod = q2;
所以就可以得出：(a * b) % mod = ( (a % mod) * (b % mod) ) % mod。

a为底数，b为指数，mod为要取余的数

举个列子：3^10 = (3^2)^5 = 9^5 = 99^4 = 9 (9^2)^2 = 9 * 81^2 = 9*(81^2)^1 直到指数为0

指数10->5,如果指数为偶数，就让指数 / 2，如果结果不变底数肯定要平方；

指数5->2,如果指数为奇数，也让指数 / 2，但是肯定要先提出一个底数来，才能配出偶数的幂

using namespace std;

typedef long long LL;

LL fast_power(LL a,LL b,LL mod)
{
    LL ans=1;   //记录结果
    a%=mod;   //为了防止输入过大
    while(b)
    {
        //如果b(指数)为奇数，就先拿出来一个，先让结果乘了
        if(b&1){  //也就是(b%2!=0),因为二进制中只有当有第一位1的时候才能为奇数
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;  //底数平方
        b>>=1;   //也就是b/2,(指数除二)让底数平方
    }
    return ans%mod;  //最后还得除mod，因为(a * b) % mod = ( (a % mod) * (b % mod) ) % mod。
}
int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    cout<<fast_power(a,b,p)<<endl;
}