#include <stdio.h>

 

typedef long long LL;

LL exp_mod(LL a,LL n,int m)//a^n(mod m)
{
    //141MS
    int bit[64],i=0;
    while(n)
    {
        bit[i++] = n & 1;
        n >>= 1;
    }
    LL s = 1;
    for(int j=i-1; j>=0; j–)
    {
        s = s * s % m;
        if(bit[j]) s = s * a % m;
    }
    return s;
   
    /*157MS
    if(!n) return 1 % m;
    if(n == 1) return a % m;
    LL t = exp_mod(a, n/2, m);
    t = t * t % m;
    if(n & 1) t = t * a % m;
    return t;*/

    /*125MS
    LL s=1;
    while(n)
    {
        if(n & 1) s = s * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return s;*/
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen(“tdata.txt”,”r”,stdin);
#endif
    int Z;
    scanf(“%d”,&Z);
    LL a,b,sum;
    int h,m;
    while(Z–)
    {
        sum=0;
        scanf(“%d %d”,&m,&h);
        while(h–)
        {
            scanf(“%I64d %I64d”,&a,&b);
            sum += exp_mod(a,b,m);
            sum %= m;
        }
        printf(“%I64d\n”,sum);
    }
    return 0;
}


版权声明：本文为feature原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/feature/articles/1823797.html