1995:Raising Modulo Numbers

keyword

べき乗　C++

概要

A_iとB_iとMが与えられたときsum(A_i^B_i) (mod M)を求める問題。数列の長さやMは45000以下。
AとBに関する制限は不明だけどさすがにintには収まるだろうと信じる。べき乗はO(log n)で計算できるので後は書くだけで良い。

inline ll powMod(ll base, ll n, ll mod){
    if(!n) return 1;
    if(n&1) return base*powMod(base,n-1,mod)%mod;
    return powMod(base*base%mod, n>>1, mod);
}

int main(){
    ll rept, i, m, n, a, b, ans;
    scanf("%lld",&rept);

    while(rept--){
        scanf("%lld",&m);
        scanf("%lld",&n);
        ans = 0;
        REP(i,n){
            scanf("%lld%lld",&a,&b);
            ans += powMod(a,b,m);
        }
        printf("%lld\n",ans%m);
    }

    return 0;
}