题目大意

对于给定的正整数 $n$ ，定义函数 $f(n)$ 如下：

$$f(n)=\sum _{\begin{array}{c}1\le p\le q\le n\\ \mathrm{lcm}(p,q)=n\end{array}}(p+q)$$

换句话说， $f(n)$ 是所有满足 $p\le q$ 且 $p$ 和 $q$ 的最小公倍数等于 $n$ 的数对 $(p,q)$ 的和 $(p+q)$ 的总和。

现在题目会给出 $n$ 的质因数分解形式，要求计算 $f(n)\mathrm{mod}1000000007$ 。

输入格式

第一行是测试用例数 $T$ （ $T\le 500$ ）。
每个测试用例首先是一个整数 $C$ （ $C\le 15$ ），表示 $n$ 的质因子个数。
接下来 $C$ 行，每行两个整数 $P_i$ 和 $a_i$ ，表示一个质因子及其指数（ $P_i$ 是 $2$ 到 $1000$ 之间的素数， $1\le a_i\le 50$ ，所有质因子互不相同）。

输出格式

对于每个测试用例，输出一行 Case i: result ，其中 $i$ 是编号， $result$ 是 $f(n)\mathrm{mod}1000000007$ 的结果。

题目分析与思路

这是一个需要推导数学公式的数论问题。直接枚举所有可能的 $p$ 和 $q$ 是不可行的，因为 $n$ 可以很大（质因数分解形式下， $n$ 本身可能远超 $10^{100}$ ）。我们需要利用 $\mathrm{lcm}(p,q)=n$ 的条件以及积性函数的性质。

1. 关键定义

首先定义两个辅助函数：

• $f(n)$ ：即题目所求，只考虑 $p\le q$ 的无序对。
• $F(n)$ ：考虑所有有序对 $(p,q)$ （包括 $p>q$ ）的和：
  $$F(n)=\sum _{i=1}^n\sum _{j=1}^n(i+j)\cdot [\mathrm{lcm}(i,j)=n]$$
  其中 $[P]$ 是指示函数，当 $P$ 为真时值为 $1$ ，否则为 $0$ 。

2. $f(n)$ 与 $F(n)$ 的关系

由于 $F(n)$ 计算了所有有序对，而 $f(n)$ 只计算了 $p\le q$ 的情况，并且当 $p=q=n$ 时， $f(n)$ 只计算一次 $2n$ ，而 $F(n)$ 也计算一次 $2n$ 。它们的关系可以通过对称性推导：

$$F(n)=2f(n)-2n$$

推导如下：在 $F(n)$ 中，对于 $p<q$ 的无序对，每个会被计算两次（ $(p,q)$ 和 $(q,p)$ ）；对于 $p=q$ 的情况，只有 $p=q=n$ 满足 $\mathrm{lcm}=n$ ，这个对在 $F(n)$ 中被算一次，在 $f(n)$ 中也只算一次。因此 $F(n)=2f(n)-2n$ （因为 $f(n)$ 中 $(n,n)$ 的和是 $2n$ ，在 $F(n)$ 中也是 $2n$ ，但对称求和时多减了一次，调整后得到此式）。

3. 对于素数幂 $p^a$ 的 $F(p^a)$

这是推导的核心。我们需要计算当 $n=p^a$ 时，所有有序对 $(p^x,p^y)$ 满足 $\max (x,y)=a$ 的和 $p^x+p^y$ 。

经过推导（具体过程涉及分类讨论 $x$ 和 $y$ 的取值），得到公式：

• 当 $a=1$ 时：
  $$F(p)=4p+2$$

• 当 $a\ge 2$ 时：
  $$F(p^a)=2(a+1)p^a+\frac{2(p^a-p)}{p-1}+2$$

4. 一般 $n$ 的 $F(n)$ 与 $f(n)$

由于 $\mathrm{lcm}(p,q)=n$ 的条件在不同质因子上是独立的， $F(n)$ 是一个积性函数。因此，对于 $n={\prod }_{i=1}^k{p}_i^{a_i}$ ，有：

$$F(n)=\frac{{\prod }_{i=1}^{k}F(p_i^{a_i})}{2^{k-1}}$$

这里除以 $2^{k-1}$ 是为了修正每个质因子独立计算时引入的重复对称因子。

然后，利用 $f(n)=\frac{F(n)+2n}{2}$ ，我们可以得到：

$$f(n)=n+\frac{{\prod }_{i=1}^{k}F(p_i^{a_i})}{2^k}$$

5. 算法步骤

1. 读取 $C$ 和每个质因子 $p_i,a_i$ 。
2. 计算 $n=\prod p_i^{a_i}\mathrm{mod}M$ （ $M=10^9+7$ ）。
3. 对每个质因子，根据 $a_i$ 的值计算 $F(p_i^{a_i})\mathrm{mod}M$ 。注意公式中的除法需要使用模逆元。
4. 计算所有 $F(p_i^{a_i})$ 的乘积 $\mathrm{mod}M$ 。
5. 计算 $2^{-k}\mathrm{mod}M$ ，即 $inv{2}^k$ ，其中 $inv2=(M+1)/2$ 是 $2$ 的模逆元。
6. 最终答案：
   $$ans=\left(n+prodF\times inv{2}^k\right)\mathrm{mod}M$$

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

// 快速幂取模
ll powMod(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        int C; cin >> C;
        ll n = 1;                 // n 模 MOD
        ll prodF = 1;             // 所有 F(p_i^{a_i}) 的乘积
        ll inv2 = (MOD + 1) / 2;  // 2 的模逆元
        ll inv2k = 1;             // 2^{-k} 的模逆元
        while (C--) {
            ll p, a; cin >> p >> a;
            ll pa = powMod(p, a); // p^a mod MOD
            n = n * pa % MOD;     // 累积计算 n mod MOD

            ll Fi; // 计算 F(p^a) mod MOD
            if (a == 1) {
                // 公式: F(p) = 4p + 2
                Fi = (4 * pa + 2) % MOD;
            } else {
                // 公式: F(p^a) = 2(a+1)p^a + 2(p^a - p)/(p-1) + 2
                ll term1 = 2 * (a + 1) % MOD * pa % MOD;
                // 注意 (p^a - p) 可能为负，先加 MOD
                ll term2 = 2 * (pa - p + MOD) % MOD * powMod(p - 1, MOD - 2) % MOD;
                Fi = (term1 + term2 + 2) % MOD;
            }
            prodF = prodF * Fi % MOD;
            inv2k = inv2k * inv2 % MOD; // 累积 2^{-k}
        }
        ll ans = (n + prodF * inv2k % MOD) % MOD;
        cout << "Case " << cas << ": " << ans << "\n";
    }
    return 0;
}

复杂度分析

• 时间复杂度：对于每个测试用例，需要计算 $C$ 个 $F(p_i^{a_i})$ ，每个计算涉及 $O(\log a_i)$ 的快速幂和常数次模运算。总复杂度为 $O(C\log a_i)$ ，完全可行。
• 空间复杂度： $O(1)$ 。

总结

本题的关键在于将原问题转化为求 $F(n)$ ，并利用积性函数的性质，将 $F(n)$ 分解为各质因子幂的 $F(p^a)$ 的乘积。推导出 $F(p^a)$ 的闭合公式后，即可在模意义下高效计算。在实现时需要注意模逆元的处理以及负数取模的细节。