【牛客小白月赛12】华华教月月做数学（快速幂+快速乘------模版题）

题目：

---

https://ac.nowcoder.com/acm/contest/392/B

给定正整数A、B、P，求A的B次方模P的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。
因为月月的作业很多，所以有T组询问。

输入描述:

第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。

1<=T<=1e3,1<=A,B,P<=1e18

输出描述:

输出T行，每行一个非负整数表示答案。

输入

2
2 5 10
57284938291657 827493857294857 384729583748273

输出

2
18924650048745

解题思路：

---

大整数幂，快速幂+快速乘模版题，具体实现看代码。

两个数相乘的时候会爆long long ,要用快速乘，快速乘与快速幂相似，把*变成+即可

注意：求快速幂的时候在mian中写迭代的写法，避免调用超时

 

ac代码：

---

#include <bits/stdc++>
#include <sstream>
#define maxn 20005
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll a,b,p;
ll quick_mul(ll a,ll b)
{
    ll r=0,t=a;
    while(b>0)
    {
        if(b&1)
            r=(r+t)%p;
        t=(t<<1)%p;
        b>>=1;
    }
    return r%p;
}
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %lld %lld",&a,&b,&p);
        ll ans=1;
        while(b>0)
        {
            if(b&1)
                ans=quick_mul(ans,a)%p;
            a=quick_mul(a,a)%p;
            b>>=1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}