题目链接

Raising Modulo Numbers POJ - 1995

思路

$$ 快速幂模板题 $$

时间复杂度

$$ O(log(N)) $$

代码

#include <cstdio>

using namespace std;

int pow_mod(int a, int b, int mod) {
    int res = 1;
    res %= mod;
    while (b) {
        if (b & 1) {
            res = 1LL * res * a % mod;
        }
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {

    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        int m;
        scanf("%d", &m);// don't forget &
        int n;
        scanf("%d", &n);// don't forget &
        int ans = 0;
        while (n--) {
            int x, y;
            scanf("%d%d", &x, &y);// don't forget &
            ans += pow_mod(x, y, m);
            if (ans >= m) {
                ans -= m;
            }
        }
        printf("%d\n", ans);
    }


    return 0;
}