【poj1995】快速幂

题目大意

求a^b %p
1≤a,b,p≤10^9

思路

时间O(10^9)一定会爆T，采用数学方法+位运算，得到O（log b)的快速幂算法

代码

#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;

inline int read()
{
    int ans=0,f=1;
    char chr=getchar();
    while(!isdigit(chr)) {if(chr='-') f=-1; chr=getchar();}
    while(isdigit(chr)) {ans=ans*10+chr-'0'; chr=getchar();}
    return ans*f;
}
ll T,p; 
int n;

ll calc(ll a,ll b,ll c)//计算a^b%p
{
    ll tans=1;//记录答案
    while(b)
    {
        if(b&1) tans=tans*a%p;//如果是奇数，意味着这一处数位要取，更新ans;
        a=a*a%p;//更新a；
        b>>=1;//将b左移一位
    }
    return tans;
}
int main()
{
    T=read();
    while(T--)
    {
        ll ans=0;
        p=read();
        n=read();
        for(int i=1;i<=n;i++)
        {
            ll a=read(),b=read();
            ans=(ans+calc(a,b,p))%p;
        }
        printf("%d\n",ans);
    }
    return 0;
}