POJ3641

此题应归类为素数。

POJ1995

http://poj.org/problem?id=1995

题意

求(A1^B1+A2^B2+ … +AH^BH)mod M.

思路

标准快速幂运算题目，算法复杂度为logN。不需要解释，直接看代码好了。

代码

Source Code

Problem: 1995       User: liangrx06

Memory: 204K        Time: 329MS

Language: C++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

using namespace std;

int main(void)

{

    int z, m, h;

    long long a, b, res, sum;

    cin >> z;

    while (z --) {

        cin >> m >> h;

        sum = 0;

        for (int i = 0; i < h; i ++) {

            cin >> a >> b;

            res = 1;

            while (b) {

                if (b % 2 == 1)

                    res = (res * a) % m;

                a = (a * a) % m;

                b /= 2;

            }

            sum = (sum + res) % m;

        }

        printf("%lld\n", sum);

    }

    return 0;

}