🔍 题目核心思路

题目要求计算：

$$\sum_{i=1}^n\sum_{j=1}^m\sigma(\gcd(i,j))[\sigma(\gcd(i,j))\leqslant a] \mod 2^{31} $$

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

1. 枚举gcd与莫比乌斯反演：
   首先枚举 $d = \gcd(i, j)$，利用莫比乌斯反演，式子可化为：

   $$\sum_{d=1}^{\min(n,m)} \sigma(d) [\sigma(d) \leqslant a] \sum_{x=1}^{\min(\lfloor n/d \rfloor, \lfloor m/d \rfloor)} \mu(x) \left\lfloor \frac{n}{dx} \right\rfloor \left\lfloor \frac{m}{dx} \right\rfloor $$

   再令 $k = dx$，则进一步化为：

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

   设 $f(k) = \sum_{d|k} \sigma(d) \mu(k/d)$，若无 $a$ 的限制，则 $f(k) = k$（即恒等函数 $id$）。

2. 处理 $a$ 的限制：
   $[\sigma(d) \leqslant a]$ 的限制使得我们无法直接使用 $f(k)=k$。

   • 关键技巧：将查询按 $a$ 升序排序，同时将 $\sigma(d)$ 按升序排序。
   • 按 $a$ 从小到大处理询问，将满足 $\sigma(d) \leqslant a$ 的 $d$ 逐步加入，更新其倍数 $k$ 对应的 $f(k)$ 值（即加上 $\sigma(d) \mu(k/d)$）。
   • 由于 $\sigma(d)$ 有序，每个 $d$ 只会被加入一次。
   • 询问时，利用数论分块和树状数组（或线段树）快速计算 $\sum_{k=1}^{\min(n,m)} \lfloor n/k \rfloor \lfloor m/k \rfloor f(k)$。

📊 算法步骤与优化

• 预处理：
  • 线性筛预处理 $\mu(n)$ 和 $\sigma(n)$。
  • 将 $\sigma(d)$ 与其对应的 $d$ 一起存储，并按 $\sigma(d)$ 排序。
• 处理询问：
  1. 将询问按 $a$ 升序排序。
  2. 使用指针将满足 $\sigma(d) \leqslant a_{\text{当前}}$ 的 $d$ 加入：对每个 $d$，枚举其倍数 $k$，在树状数组中更新 $f(k) += \sigma(d) \cdot \mu(k/d)$。
  3. 对于每个询问 $(n, m, a)$，利用数论分块和树状数组查询区间和快速计算答案。
• 复杂度分析：
  • 预处理 $O(N \log N)$。
  • 每个 $d$ 的加入操作是其倍数枚举，复杂度为 $O(N \log N)$。
  • 每个询问通过数论分块和树状数组查询，复杂度为 $O(\sqrt{N} \log N)$。

💡 关键点与注意事项

• 思路转换：通过将询问按 $a$ 排序，并逐步加入满足条件的 $d$，巧妙地处理了 $a$ 的限制。
• 数据结构应用：需要动态维护 $f(k)$ 并支持快速区间查询，树状数组是不错的选择。
• 模数处理：模数为 $2^{31}$，可以使用自然溢出（unsigned int）或直接取模。

📝 代码实现提示

由于完整的代码较长，这里给出核心部分的实现思路：

1. 预处理 $\mu$ 和 $\sigma$：

   // 线性筛预处理 mu 和 sigma
   vector<int> mu(N), sigma(N);
   // ... 线性筛代码 ...
   

2. 存储 $\sigma(d)$ 和 $d$：

   vector<pair<int, int>> sig_d;
   for (int i = 1; i < N; i++) {
       sig_d.push_back({sigma[i], i});
   }
   sort(sig_d.begin(), sig_d.end());
   

3. 处理询问（需树状数组支持）：

   // 将询问按a排序后，依次处理
   int idx = 0;
   for (auto &q : queries) {
       while (idx < sig_d.size() && sig_d[idx].first <= q.a) {
           int d = sig_d[idx].second;
           for (int k = d; k < N; k += d) {
               // 更新树状数组：f(k) += sigma[d] * mu[k/d]
               bit.update(k, sigma[d] * mu[k/d]);
           }
           idx++;
       }
       // 数论分块计算答案
       long long ans = 0;
       for (int l = 1, r; l <= min(q.n, q.m); l = r + 1) {
           r = min(q.n / (q.n / l), q.m / (q.m / l));
           ans += (bit.query(r) - bit.query(l - 1)) * (q.n / l) * (q.m / l);
       }
       // 记录答案
   }
   

💎 总结

这道题的核心在于将询问排序后离线处理，并结合莫比乌斯反演、数论分块和树状数组来高效计算。关键在于理解如何通过排序 $a$ 和 $\sigma(d)$，将限制条件转化为动态的因子加入过程。