这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门: http://acm.pku.edu.cn/JudgeOnline/problem?id=1995
以下是AC代码:
// Author: Tanky woo
// POJ 1995
// www.wutianqi.com
#include
using namespace std;
int nCases;
__int64 nNum, M, H, a, b;
__int64 exp_mod(__int64 a, __int64 n, __int64 b)
{
__int64 t;
if(n==0) return 1%b;
if(n==1) return a%b;
t=exp_mod(a,n/2,b);
t=t*t%b;
if((n&1)==1) t=t*a%b;
return t;
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &nCases;);
while(nCases--)
{
__int64 ans = 0;
scanf("%I64d %I64d", &M;, &H;);
while(H--)
{
scanf("%I64d %I64d", &a;, &b;);
ans += exp_mod(a, b, M);
ans %= M;
}
printf("%I64d\n", ans);
}
return 0;
}
具体分析见: 快速幂取模