POJ-1995

在此之前需要知道两个知识点。

第一个是快速幂，在的时间内求出的值。
这个算法事实上就是二进制的思想，将b看成是二进制的数来进行分割。
鉴于这个网上博客已经讲到烂了（跟欧几里得算法差不多简单），我就不再啰嗦了。

第二个是分步取余。对于只有加法，减法，乘法的运算中，满足如下性质：

(a+b)%m=((a%m)+(b%m))%m
(a-b)%m=((a%m)-(b%m))%m
(a*b)%m=((a%m)*(b%m))%m

由于乘方事实上就是多次乘法，所以也符合上面的性质。
也就是说，如果不包含除法的话，你可以在整个运算中的任意位置对数字进行取余，都不影响结果。

关于这个的证明如下：

首先假设a=a1+a2*c,b=b1+b2*c，其中a1和b1是a%c和b%c的结果
于是就有：
(a+b)%c=(a1+a2*c+b1+b2*c)%c=(a1+b1)%c+((a2+b2)*c)%c=(a1+b1)%c=((a%c)+(b%c))%c
(a-b)%c=(a1+a2*c-b1-b2*c)%c=(a1-b1)%c+((a2-b2)*c)%c=(a1-b1)%c=((a%c)-(b%c))%c
(a*b)%c=((a1+a2*c)*(b1+b2*c))%c=(a1*b1)%c+((a1*b2+a2*b1+a2*b2*c)*c)%c=(a1*b1)%c=((a%c)*(b%c))%c
证毕

事实上也很好理解，就是把a和b切割掉c的倍数的部分再进行运算。

而至于除法的，详见群文件，那里有长篇大论讲这个的。由于这里并不涉及就不详细展开了。

于是我们可以知道，在求问题中的式子的时候，我们可以在其快要溢出的时候先对m取余，防止它接下来会溢出，再进行接下去的操作。
那么代码中怎么处理呢？简单粗暴的方法是在每一次运算后都对m取余。（事实上我就是这样做的）

那么，知道这两个知识的话，问题就变得十分简单了，照着它说的做就行了。

#include <cstdio>

using namespace std;

typedef long long LL;

LL Pow(LL a,LL b,LL m)
{
    LL ret=1;
    while(b)
    {
        if(b&1)ret=(ret*a)%m;
        a=(a*a)%m;
        b>>=1;
    }
    return ret;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL m;
        scanf("%lld",&m);
        int n;
        scanf("%d",&n);
        LL ans=0;
        while(n--)
        {
            LL a,b;
            scanf("%lld%lld",&a,&b);
            ans=(ans+Pow(a,b,m))%m;
        }
        printf("%d\n",ans);
    }
    return 0;
}