http://poj.org/problem?id=1995
以这道题来分析一下快速幂取模
a^b%c（这就是著名的RSA公钥的加密方法），当a,b很大时，直接求解这个问题不太可能
利用公式a*b%c=((a%c)*b)%c
每一步都进行这种处理，这就解决了a^b可能太大存不下的问题，但这个算法的时间复杂度依然没有得到优化
由此可以用快速幂算法优化：
http://www.cnblogs.com/qlky/p/5020402.html
再结合取模公式：
(a + b) % p = (a % p + b % p) % p
http://www.cnblogs.com/qlky/p/5020632.html
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm> using namespace std; long long mod(long long a,long long b,long long m)
{
long long r =,base = a;
while(b!=)
{
if(b&)
r= r*base%m;
base= base*base%m;
b>>=;
}
return r;
} int main()
{
long long t,n,m,i;
long long sum = ;
scanf("%lld",&t);
while (t--)
{
scanf("%lld%lld",&m,&n); long long a,b;
scanf("%lld%lld",&a,&b);
sum = mod(a,b,m); for(i = ;i<n-;i++)
{
scanf("%lld%lld",&a,&b);
sum+=mod(a,b,m);
sum%=m;
}
printf("%lld\n",sum); }
return ;
}