poj 1995 裸快速幂

#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f

int main()
{
    int z,n,m;
    LL a,b;
    LL sum,s;
    scanf("%d",&z);
    while(z--)
    {
        scanf("%d",&m);
        scanf("%d",&n);
        sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%lld%lld",&a,&b);
            s=1;
            while(b)
            {
                if(b&1){       //b二进制最后一位是1就执行这步
                    s=(s*a)%m;  //即b为偶数不执行，b为奇数就让s累加b除2后剩下的
                }

                b/=2;
                a=(a*a)%m;     //即a^b=(a^2)^(b>>1)
            }

            sum+=(s%m);
        }
        printf("%lld\n",sum%m);
    }

    return 0;
}