*题目描述 *
People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow:

Each player chooses two numbers Ai and Bi writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions 图片说明

from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers.

You should write a program that calculates the result and is able to find out who won the game.

输入描述:
The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 \leq M \leq 45000)(1≤M≤45000). The sum will be divided by this number. Next line contains number of players H(1 \leq M \leq 45000)(1≤M≤45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time.
输出描述:
For each assingnement there is the only one line of output. On this line, there is a number, the result of expression
图片说明

大概题意：
读不懂？没关系，我英语也不是很好，不过只要大概知道输入和输出就行了吧：
第一行输入t,代表要测试t组数；第二行输入m,表示对m求模；，第三行输入n表示接下来要有n行数据，该n行数据每行包含2个数a,b;求这n个a^b的和，并计算该和对m求模的值

思路：
不用我说，这道题使用快速幂做的，因为直接算的话，时间复杂度就太大了。能快速算出a的b次幂，就能减小时间复杂度。

什么是快速幂与时间复杂度分析：
快速幂是一种简化运算底数的n次幂的算法，理论上其时间复杂度为 O(log₂N)，而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就是抽取了指数中的2的n次幂，将其转换为时间复杂度为O(1)的二进制移位运算，所以相应地，时间复杂度降低为O(log₂N)。

代码原理：
以a^13为例，
先把指数13化为二进制就是1101，把二进制数字1101直观地表现为十进制则是如下的等式：
13 = 1 * (2^3) + 1 * (2^2) + 0 * (2^ 1) + 1 * (2^0)
这样一来a^13可以如下算出：
a^13 = a ^ (2^3) * a ^ (2^2) * a ^ (2^0)

完整C++版AC代码：

#include <iostream>

using namespace std;

typedef long long ll;

ll ksm(ll a,ll b,ll p) {
    ll ans = 1;
    while (b > 0) {
        if (b & 1) {
            ans = ans * a % p;
        }
        b = b >> 1;
        a = a * a % p;
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll ans = 0;
        ll m;
        int n;
        cin >> m >> n;

        while (n--) {

            ll a, b;
            cin >> a >> b;

            ans = (ans + ksm(a, b, m)) % m;

        }
        cout << ans << endl;
    }
    return 0;
}