Tanky WooRSS

POJ 1995 Raising Modulo Numbers

07 Sep 2010
这篇博客是从旧博客 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;
}

具体分析见: 快速幂取模