🧩 问题核心分析

题目要求计算数表中所有不超过给定值 $a$ 的数值之和。该数表第 $i$ 行第 $j$ 列的数值为：

$$\sigma(\gcd(i, j))$$

其中 $\sigma(k)$ 表示 $k$ 的约数之和。

我们需要计算的是：

$$\sum_{i=1}^n \sum_{j=1}^m \sigma(\gcd(i, j)) \cdot [\sigma(\gcd(i, j)) \leq a] $$

其中 $[P]$ 表示条件 $P$ 成立时为1，否则为0。

💡 解题思路与数学推导

🔹 第一步：利用莫比乌斯反演简化

令 $d = \gcd(i, j)$，我们可以改写求和式为：

$$\sum_{d=1}^{\min(n,m)} \sigma(d) \cdot [\sigma(d) \leq a] \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d] $$

根据莫比乌斯反演，我们知道：

$$\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d] = \sum_{k=1}^{\lfloor \min(n,m)/d \rfloor} \mu(k) \cdot \left\lfloor \frac{n}{dk} \right\rfloor \cdot \left\lfloor \frac{m}{dk} \right\rfloor $$

令 $T = dk$，则上式变为：

$$\sum_{T=1}^{\min(n,m)} \left\lfloor \frac{n}{T} \right\rfloor \cdot \left\lfloor \frac{m}{T} \right\rfloor \sum_{d|T} \sigma(d) \cdot [\sigma(d) \leq a] \cdot \mu\left(\frac{T}{d}\right) $$

🔹 第二步：处理 $a$ 的限制条件

$a$ 的限制使得问题变得复杂，因为我们需要动态考虑哪些 $\sigma(d)$ 满足条件。解决方法是：

1. 离线处理：将所有查询按 $a$ 从小到大排序
2. 动态维护：当 $a$ 增大时，将满足 $\sigma(d) \leq a$ 的 $d$ 加入贡献

定义：

$$F(T) = \sum_{d|T} \sigma(d) \cdot \mu\left(\frac{T}{d}\right) $$

但受 $a$ 限制，实际考虑的是：

$$F_a(T) = \sum_{d|T} \sigma(d) \cdot [\sigma(d) \leq a] \cdot \mu\left(\frac{T}{d}\right) $$

🔹 第三步：使用树状数组维护前缀和

我们需要动态维护 $G(T) = F_a(T)$ 的前缀和，以便利用数论分块计算答案。具体步骤：

1. 预处理：

   • $\mu(n)$：莫比乌斯函数
   • $\sigma(n)$：约数函数
   • 将 $\sigma(d)$ 按值排序

2. 算法流程：

   • 将查询按 $a$ 排序
   • 按 $\sigma(d)$ 从小到大的顺序，将每个 $d$ 的贡献加到所有 $T$ 满足 $d|T$ 的 $F(T)$ 中
   • 用树状数组维护 $F(T)$ 的前缀和
   • 对于每个查询，使用数论分块计算：$$\sum_{T=1}^{\min(n,m)} \left\lfloor \frac{n}{T} \right\rfloor \cdot \left\lfloor \frac{m}{T} \right\rfloor \cdot F_a(T) $$

🧮 核心算法实现

预处理代码框架

const int N = 100000;

// 预处理莫比乌斯函数和约数函数
void init() {
    vector<int> mu(N+1), sigma(N+1), primes;
    vector<bool> is_prime(N+1, true);
    
    mu[1] = 1;
    sigma[1] = 1;
    
    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            mu[i] = -1;
            sigma[i] = i + 1;
        }
        for (int p : primes) {
            if (i * p > N) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                mu[i * p] = 0;
                // 计算 sigma[i * p]，需要记录最小质因子的幂次
                break;
            } else {
                mu[i * p] = -mu[i];
                sigma[i * p] = sigma[i] * sigma[p];
            }
        }
    }
}

主算法框架

struct Query {
    int n, m, a, id;
};

struct DivisorSigma {
    int sigma, d;
};

void solve() {
    // 预处理 mu, sigma
    init();
    
    // 准备约数函数值的排序
    vector<DivisorSigma> ds;
    for (int d = 1; d <= N; d++) {
        ds.push_back({sigma[d], d});
    }
    sort(ds.begin(), ds.end(), [](const DivisorSigma& x, const DivisorSigma& y) {
        return x.sigma < y.sigma;
    });
    
    // 读入查询并排序
    vector<Query> queries;
    // ... 读入数据
    sort(queries.begin(), queries.end(), [](const Query& x, const Query& y) {
        return x.a < y.a;
    });
    
    // 树状数组维护 F(T) 前缀和
    FenwickTree tree(N);
    
    int pos = 0; // 当前处理到的 ds 位置
    for (auto& q : queries) {
        // 将 sigma(d) <= q.a 的贡献加入
        while (pos < ds.size() && ds[pos].sigma <= q.a) {
            int d = ds[pos].d;
            // 将 d 的贡献加到所有 T = k*d 的 F(T) 中
            for (int T = d; T <= N; T += d) {
                tree.add(T, sigma[d] * mu[T / d]);
            }
            pos++;
        }
        
        // 计算答案
        int ans = 0;
        int nm = min(q.n, q.m);
        for (int l = 1, r; l <= nm; l = r + 1) {
            r = min(q.n / (q.n / l), q.m / (q.m / l));
            int sum = tree.sum(r) - tree.sum(l - 1);
            ans += (q.n / l) * (q.m / l) * sum;
        }
        // 输出答案，注意模 2^31
    }
}

⚠️ 实现细节与优化

1. 模运算技巧：

   • 模 $2^{31}$ 可以用 & ((1LL << 31) - 1) 实现
   • 注意处理负数：(x + mod) & mod_mask

2. 复杂度分析：

   • 预处理：$O(N \log N)$
   • 主算法：$O(N \log^2 N + Q \sqrt{N} \log N)$
   • 可以通过 $n, m \leq 10^5$ 的约束

3. 优化方向：

   • 使用欧拉筛线性预处理 $\mu$ 和 $\sigma$
   • 批量处理约数贡献，减少树状数组操作

💎 总结

本题的解题关键在于：

1. 莫比乌斯反演：将二维求和转化为约数相关的表达式
2. 离线处理：通过按 $a$ 排序查询，动态维护贡献
3. 树状数组：高效维护数论函数的前缀和
4. 数论分块：快速计算包含下取整的求和式