快速幂算法通常用在求  A^B%C 的时候，因为当B足够大的时候 n与logn 的差距就非常巨大了。并且B十分巨大的时候通常我们已经存不下这个数值了。所以一般要对一个C 取模。
如果B十分大，那么有可能会产生a的2^n次方时比 long long 还大。这时就有可能输出负数也就是溢出了。所以这个时候可以用加法来模拟乘法，并且每次相加都对C取模，这样就不会溢出了。
加法模拟乘法：
列如：求7*5：
n=5的二进制是101， 
此时n为奇数，则ans=ans+tmp；tmp=tmp+tmp；n右移一位；（ans=0+7，tmp=7*2） 
此时n为偶数，则直接tmp=tmp+tmp；n右移一位；（ans=7，tmp=7*4） 
此时n为奇数，则ans=ans+tmp；tmp=tmp+tmp；n右移一位；（ans=7+7*4，tmp=7*8）; 
快速幂算法：https://blog.csdn.net/wuyileiju__/article/details/81056150
列如求5^19:
n=19的二进制是10011， 
此时n为奇数，则ans=ans*tmp；tmp=tmp*tmp；n右移一位；（ans=1*5，tmp=5*5=25） 
此时n为奇数，则ans=ans*tmp；tmp=tmp*tmp；n右移一位；（ans=5*25，tmp=25*25） 
此时n为偶数，则直接tmp=tmp*tmp；n右移一位；（ans=125，tmp=625*625） 
此时n为偶数，则直接tmp=tmp*tmp；n右移一位；（ans=125，tmp=390625*390625） 
此时n为奇数，则ans=ans*tmp；tmp=tmp*tmp；n右移一位；（ans=125*390625*390625，tmp=(390625*390625）^2）; 
模板： 
#include<bits/stdc++.h>
using namespace std;
long long pow_mul(long long a,long long b,long long mod)
{
    long long ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}
long long pow_mod(long long a,long long b,long long mod)
{
    long long ans=1;
	
    while(b)
    {
        if(b&1) ans=pow_mul(ans,a,mod);
        a=pow_mul(a,a,mod);
        b>>=1;
    }
    return ans;
}
int main()
{
    long long t,a,b,p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&a,&b,&p);
        printf("%lld\n",pow_mod(a,b,p));
    }
    return 0;
}