题目理解

我们有 $n$ 支队伍，每队 $m$ 个划手。对于第 $i$ 支队伍，其能力比值为：

$$c_i = \frac{\prod_{j=1}^m b_j}{\prod_{j=1}^m a_{i,j}} $$

其中 $b_j$ 是标准能力值，$a_{i,j}$ 是第 $i$ 队第 $j$ 个划手的能力值。

在模 $M$ 压力下，表现值为：

$$C \equiv \frac{\prod_{j=1}^m b_j}{\prod_{j=1}^m a_{i,j}} \pmod{M} $$

即需要计算分数在模 $M$ 意义下的值，如果分母在模 $M$ 下不可逆，则输出 $-1$。

---

核心思路

1. 问题转化

计算：

$$C \equiv \left(\prod_{j=1}^m b_j\right) \times \left(\prod_{j=1}^m a_{i,j}\right)^{-1} \pmod{M} $$

关键难点：$M$ 可能不是质数，分母的逆元不一定存在。

---

2. 解决方案

将 $M$ 质因数分解：$M = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$

对于每个质因子 $p_i$，分别处理分子和分母中 $p_i$ 的指数：

• 如果分母中某个 $p_i$ 的指数大于分子，则逆元不存在
• 否则，将 $p_i$ 的因子完全提取出来，剩余部分与 $M$ 互质，可以求逆元

---

算法步骤

步骤 1：质因数分解

使用 Miller-Rabin 质数测试和 Pollard Rho 算法分解 $M$。

步骤 2：提取质因子

对分子 $\prod b_j$ 和分母 $\prod a_{i,j}$，分别提取出 $M$ 的所有质因子，记录指数差。

步骤 3：检查可行性

如果对于任何质因子 $p_i$，分母中的指数大于分子，则逆元不存在。

步骤 4：计算最终结果

将质因子部分与互质部分分开计算：

• 质因子部分直接乘幂
• 互质部分用欧拉定理求逆元：$x^{-1} \equiv x^{\phi(M)-1} \pmod{M}$

---

代码解析

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128  // 用于处理大数乘法

const int test[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const int N = 25, M = 1e4 + 5;

int n, m, k, tot, id;
ll p;
ll a[N][M], b[M], d[M], T[M], ta[M], tb[M];
mt19937_64 Rnd(time(0) + 20100511);

// 快速幂算法 (支持大模数)
ll QuickPow(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

// Miller-Rabin 质数测试的辅助函数
bool Check(int a, ll p) {
    ll d = p - 1, get = QuickPow(a, d, p);
    if (get != 1) return true;
    
    while ((d & 1) ^ 1) {
        if (d >>= 1, (get = QuickPow(a, d, p)) == p - 1)
            return false;
        else if (get != 1)
            return true;
    }
    return false;
}

// Miller-Rabin 质数测试
bool Miller_Rabin(ll p) {
    if (p > 40) {
        for (int a : test) {
            if (Check(a, p))
                return false;
        }
        return true;
    }
    
    for (int a : test) {
        if (a == p)
            return true;
    }
    return false;
}

// 最大公约数
ll Gcd(ll a, ll b) {
    if (b == 0) return a;
    return Gcd(b, a % b);
}

// Pollard Rho 的迭代函数
ll f(ll x, ll c, ll p) {
    return ((LL)x * x % p + c) % p;
}

// Pollard Rho 大数分解算法
ll Pollard_Rho(ll x) {
    ll s = 0, t = 0, c = Rnd() % (x - 1) + 1;
    int stp = 0, goal = 1;
    ll val = 1;

    for (goal = 1;; goal <<= 1, s = t, val = 1) {
        for (stp = 1; stp <= goal; stp++) {
            t = f(t, c, x);
            val = (LL)val * abs(t - s) % x;
            
            if (stp % 127 == 0) {
                ll d = Gcd(val, x);
                if (d > 1) return d;
            }
        }
        
        ll d = Gcd(val, x);
        if (d > 1) return d;
    }
}

// 分解质因数
void Div(ll x) {
    if (x == 1) return;
    
    if (Miller_Rabin(x)) {
        d[++tot] = x;
        return;
    }
    
    ll p = x;
    while (p >= x)
        p = Pollard_Rho(x);
        
    while (x % p == 0)
        x /= p;
        
    Div(x), Div(p);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    
    // 读入标准能力值
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    
    // 读入各队伍能力值  
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    }
    
    // 处理每个查询
    while (k--) {
        cin >> id >> p;
        tot = 0;
        
        // 分解模数 M
        Div(p);
        sort(d + 1, d + 1 + tot);
        tot = unique(d + 1, d + 1 + tot) - (d + 1);
        
        // 计算欧拉函数 φ(M)
        ll phi = p;
        for (int i = 1; i <= tot; i++)
            phi = phi / d[i] * (d[i] - 1);
        
        // 初始化质因子指数计数器
        for (int i = 1; i <= tot; i++)
            T[i] = 0;
        
        // 处理分子中的质因子
        for (int i = 1; i <= m; i++) {
            tb[i] = b[i];
            for (int j = 1; j <= tot; j++) {
                if (tb[i] % d[j] == 0) {
                    while (tb[i] % d[j] == 0) {
                        T[j]++;          // 分子质因子指数+1
                        tb[i] /= d[j];
                    }
                }
            }
        }
        
        // 处理分母中的质因子  
        for (int i = 1; i <= m; i++) {
            ta[i] = a[id][i];
            for (int j = 1; j <= tot; j++) {
                if (ta[i] % d[j] == 0) {
                    while (ta[i] % d[j] == 0) {
                        T[j]--;          // 分母质因子指数-1
                        ta[i] /= d[j];
                    }
                }
            }
        }
        
        // 检查是否存在分母质因子指数大于分子的情况
        ll A = 1, B = 1;
        bool flag = false;
        
        for (int i = 1; i <= tot; i++) {
            if (T[i] < 0) {  // 分母中该质因子指数更多
                cout << "-1\n";
                flag = true;
                break;
            } else {
                B = (LL)B * QuickPow(d[i], T[i], p) % p;
            }
        }
        
        if (flag) continue;
        
        // 计算互质部分的乘积
        for (int i = 1; i <= m; i++)
            B = (LL)B * tb[i] % p;  // 分子互质部分
            
        for (int i = 1; i <= m; i++)
            A = (LL)A * ta[i] % p;  // 分母互质部分
        
        // 计算最终结果: B × A^{-1} mod p
        B = (LL)B * QuickPow(A, phi - 1, p) % p;
        cout << B << "\n";
    }
    
    return 0;
}

---

关键算法说明

1. Miller-Rabin 质数测试

• 用于判断一个数是否为质数
• 基于费马小定理和二次探测定理
• 时间复杂度：$O(k \log n)$，其中 $k$ 是测试次数

2. Pollard Rho 大数分解

• 基于生日悖论的随机算法
• 用于分解大整数
• 期望时间复杂度：$O(n^{1/4})$

3. 欧拉定理求逆元

当 $\gcd(A, M) = 1$ 时：

$$A^{-1} \equiv A^{\phi(M)-1} \pmod{M}$$

---

复杂度分析

• 质因数分解：$O(M^{1/4})$ 每次查询
• 质因子提取：$O(m \times k)$，其中 $k$ 是质因子个数
• 总体复杂度：在数据范围内可接受

这种方法巧妙地处理了非质数模数下的分数取模问题，是数论在竞赛中的典型应用。