Posted on 2010-02-06 04:05
Uriel 阅读(382)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
数学
直接用快速模取幂的模板过的。。还记得是09' Regional 上海赛热身赛的某题数论知道式子不用快速模取幂就一直TLE。。然后从天哥大牛那里第一次知道了这个东西。。这题是第一次在POJ上用到。。
/**//*Problem: 1995 User: Uriel
Memory: 164K Time: 94MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
int a,b,t,m,res,h;
int modExp(int a, int b, int n)
{
int t = 1, y = a;
while(b != 0)
{
y %= n;
if(b % 2 == 1)
t = t % n * y % n;
y = y * y % n;
b = b >> 1;
}
return t;
}
int main()
{
int i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
scanf("%d",&h);
res=0;
for(i=0;i<h;i++)
{
scanf("%d %d",&a,&b);
res=(res+modExp(a,b,m))%m;
}
printf("%d\n",res);
}
// system("PAUSE");
return 0;
}