Posted on 2010-02-06 04:05
Uriel 閱讀(386)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
POJ 、
數(shù)學(xué)
直接用快速模取冪的模板過(guò)的。。還記得是09' Regional 上海賽熱身賽的某題數(shù)論知道式子不用快速模取冪就一直TLE。。然后從天哥大牛那里第一次知道了這個(gè)東西。。這題是第一次在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;
}