题目分析

这道题目要求我们计算多个玩家的数字对 (A_i, B_i) 的幂次和，并对给定的模数 M 取余。具体来说： 每个玩家选择两个数字 A_i 和 B_i计算每个玩家的 A_i 的 B_i 次方将所有玩家的计算结果相加对总和取模 M输出最终的模数结果

解题思路

快速幂算法：为了高效计算大数的幂次，使用快速幂算法（也称为二分幂算法）。该算法通过将指数分解为二进制形式，将时间复杂度从 O(n) 降低到 O(log n)。

模运算性质：利用模运算的性质，避免中间结果过大：

(a + b) mod m = (a mod m + b mod m) mod m

(a * b) mod m = (a mod m * b mod m) mod m

输入处理：读取测试用例数量 Z，然后逐个处理每个测试用例：

读取模数 p 和玩家数量 n

对于每个玩家，读取 A_i 和 B_i，计算 A_i^B_i mod p 并累加到总和中

每次累加后立即取模，防止数值溢出

##代码实现

#include<iostream>
using namespace std;
typedef long long LL;

// 快速幂取模函数
LL pow(LL a, LL b, LL p) {
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res % p;
}

int main() {
    int Z;
    cin >> Z;
    
    while(Z--) {
        int p, n;
        cin >> p >> n;
        
        LL ans = 0;
        for(int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            ans = (ans + pow(a, b, p)) % p;
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

代码解释

快速幂函数 pow:

参数：底数 a，指数 b，模数 p

返回值：a^b mod p

实现：通过二进制分解指数，每次将指数右移一位，底数平方，当当前位为1时将结果乘以底数

主函数 main:

读取测试用例数量 Z

对于每个测试用例：

读取模数 p 和玩家数量 n

初始化总和 ans 为 0

对于每个玩家：

读取 A_i 和 B_i

计算 A_i^B_i mod p 并累加到 ans

每次累加后立即对 p 取模

输出最终结果 ans

注意事项:

使用 long long 类型防止整数溢出

每次运算后立即取模，确保中间结果不会过大

处理输入时注意玩家编号从0开始还是从1开始（代码中从0开始）

复杂度分析

时间复杂度：O(Z * n * log b)，其中 Z 是测试用例数量，n 是玩家数量，b 是指数的最大值

空间复杂度：O(1)，仅使用常数个变量存储中间结果

示例分析 对于输入样例1：

3 16 4 2 3 3 4 4 5 5 6 计算过程：

2^3 mod 16 = 8

3^4 mod 16 = 81 mod 16 = 1

4^5 mod 16 = 1024 mod 16 = 0

5^6 mod 16 = 15625 mod 16 = 9 总和：8 + 1 + 0 + 9 = 18 18 mod 16 = 2 输出：2