题解33（快速幂与快速乘）

模板题，记住算了...想的有点晕

前言：首先要知道(a * b)%p==(a%p)*(b%p)%p;

因为这一题普通乘法用ull会超范围，只能用int128，但是int128要手写输入输出，所以还是用快速幂，快（慢）速乘算了

思路：如3^^5==3^^(0101)==3^^(2^^2+2^^0);然后每次都计算下一次

AC代码：

#include<iostream>
using namespace std;
#define ull unsigned long long
ull p;
ull quick_mul(ull a,ull b)//实现了a*b%p
{
    ull ans=0; 
    while(b)
    {
        if(b&1)
        {
            ans=(ans+a)%p;
        }
        a=(a+a)%p;//a+a即（a*2）%p
        b>>=1;
    }
    return ans;
}
ull quick_pow(ull a,ull b)
{
    ull ans=1;
    while(b)
    {
        if(b&1) 
        {
            ans=quick_mul(ans,a);//第一次就是1*a%p
        }
        a=quick_mul(a, a);//提前计算好下次的（a*b)%p中的a*p
        b>>=1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    ull a,b;//千万别在这里再定义一次p，不然输入的就不是全局变量p了
    while(t--)
    {
        cin>>a>>b>>p;
        cout<<quick_pow(a,b)<<'\n';
    }
    return 0;
}