1. 核心数学推导

题目的目标是求：

$$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C d(ijk) \pmod{10^9+7} $$

步骤一：展开 $d(ijk)$

直接计算 $d(ijk)$ 很困难，利用 $d(ijk)$ 的一个重要恒等式：

$$d(ijk) = \sum_{x|i} \sum_{y|j} \sum_{z|k} [\gcd(x, y) = 1] [\gcd(y, z) = 1] [\gcd(z, x) = 1] $$

代入原式，并交换求和顺序（先枚举 $x, y, z$），得到：

$$\sum_{x=1}^A \sum_{y=1}^B \sum_{z=1}^C \lfloor \frac{A}{x} \rfloor \lfloor \frac{B}{y} \rfloor \lfloor \frac{C}{z} \rfloor [\gcd(x, y) = 1] [\gcd(y, z) = 1] [\gcd(z, x) = 1] $$

步骤二：莫比乌斯反演

利用 $\sum_{d|n} \mu(d) = [n=1]$ 将 $\gcd$ 条件展开。 设 $u|\gcd(x, y)$， $v|\gcd(y, z)$， $w|\gcd(z, x)$。 原式变形为枚举 $u, v, w$：

$$\sum_{u, v, w} \mu(u)\mu(v)\mu(w) \sum_{x: u|x, w|x} \lfloor \frac{A}{x} \rfloor \sum_{y: u|y, v|y} \lfloor \frac{B}{y} \rfloor \sum_{z: v|z, w|z} \lfloor \frac{C}{z} \rfloor $$

注意到 $x$ 必须是 $\text{lcm}(u, w)$ 的倍数，同理 $y$ 是 $\text{lcm}(u, v)$ 的倍数，$z$ 是 $\text{lcm}(v, w)$ 的倍数。 定义辅助函数 $F(N, K) = \sum_{i=1}^{\lfloor N/K \rfloor} \lfloor \frac{N}{i \cdot K} \rfloor$。 代码中的 f[0][i]、f[1][i]、f[2][i] 分别预处理了 $A, B, C$ 对应的这个和值。例如 f[0][u] 实际上存储的是 $\sum_{k=1, u|k} \lfloor \frac{A}{k} \rfloor$，这与 $F(A, u)$ 等价（注意这里 $u$ 代表 LCM）。

最终式子转化为：

$$\sum_{u, v, w} \mu(u)\mu(v)\mu(w) \cdot f_A(\text{lcm}(u, w)) \cdot f_B(\text{lcm}(u, v)) \cdot f_C(\text{lcm}(v, w)) $$

这本质上是在寻找三元组 $(u, v, w)$，使得贡献总和最大。这就变成了一个图论问题：

• 节点是 $1 \dots N$。
• 边 $(u, v)$ 的权重是 $\text{lcm}(u, v)$。
• 我们需要统计所有三元环（及退化的点、边）的贡献。

2. 代码逻辑解析

2.1 预处理 (Init 函数)

1. 线性筛：计算 $\mu$ 函数。
2. 计算 f 数组：

   for (int j = i ; j <= n ; j += i) {
       f[ 0 ][ i ] = (f[ 0 ][ i ] + A / j) % Mod;
       // ... B和C同理
   }
   

   这里 f[0][i] 计算的是所有 $i$ 的倍数 $j$ 的 $\lfloor A/j \rfloor$ 之和，这正是推导公式中的核心部分。

2.2 建图 (Solve 函数前半部分)

我们需要枚举有效的 $(u, v)$ 对。 代码通过枚举 $d = \gcd(u, v)$，然后枚举 $i, j$ 互质来实现：

for (int d = 1 ; d <= n ; d ++)
    for (int i = 1 ; i <= n / d ; i ++)
        for (int j = i + 1 ; j <= n / i / d ; j ++)

• $u = i \times d$, $v = j \times d$。
• $l = i \times j \times d$ 即为 $\text{lcm}(u, v)$。
• 边的生成：如果 $\mu(u)$ 和 $\mu(v)$ 都不为 0，则连接边 $(u, v)$，边权为 $l$。

关于两点贡献的处理： 在建边的同时，代码顺便计算了 $u, v, w$ 中有两个数相等的情况（退化的三元环，即在一条边上来回）：

• Calc(u, l, l) 等项处理了如 $w=u$ 或 $w=v$ 的情况。

2.3 三元环计数 (Solve 函数后半部分)

这是解决本题复杂度的关键。如果我们暴力枚举 $u, v, w$，复杂度是 $O(N^3)$ 或 $O(M^2)$，无法接受。 代码使用了 三元环计数 的经典优化算法：

1. 重定向边： 将无向图转为有向图。规则是：度数小的指向度数大的；度数相同则编号小的指向编号大的。

   if (Deg[ u ] < Deg[ v ] || (Deg[ u ] == Deg[ v ] && u < v))
       Graph[ u ].push_back({ v, w });
   

   这样可以保证每个点的出度不超过 $\sqrt{M}$。

2. 枚举三元环： 枚举 $u \to v$，再枚举 $v \to w$。检查 $u, w$ 是否有边连接（通过 vt 数组标记）。

   // 枚举 u -> v
   for (int i = 0 ; i < Graph[ u ].size() ; i ++) {
       // 枚举 v -> w
       for (int j = 0 ; j < Graph[ v ].size() ; j ++) {
           // 检查 u, w 是否连通 (vt[w]存储了 u->w 的边权)
           if (vt[ w ]) { ... }
       }
   }
   

   这个过程的时间复杂度是 $O(M \sqrt{M})$，其中 $M$ 是边数。

3. 计算贡献： 对于找到的三元环 $(u, v, w)$，计算其贡献： mu[u] * mu[v] * mu[w] * (所有6种排列的 f 值乘积之和)。 因为 $A, B, C$ 不同，所以 $Calc(uw, vw, ww)$ 和 $Calc(uw, ww, vw)$ 等都需要累加。

3. 复杂度分析

• 预处理：$O(N \ln N)$，用于计算 f 数组。
• 建图：枚举 $d, i, j$ 的复杂度大约是 $O(N \log N)$ 或者接近 $O(N)$，生成的边数 $M$ 在本题数据范围内也是稀疏的。
• 三元环计数：$O(M \sqrt{M})$。

由于 $N=10^5$，这种复杂度完全可以通过。

4. 总结

这份代码通过以下步骤解决了问题：

1. 莫比乌斯反演将 $d(ijk)$ 转化为关于 $\text{lcm}$ 的式子。
2. 将式子转化为图论模型：点权为 $\mu$，边权为 $\text{lcm}$ 对应的 $f$ 值。
3. 利用三元环计数算法高效统计 $u, v, w$ 互不相同的情况。
4. 在建图过程中统计 $u, v, w$ 有重复的情况。

这是一种处理多变量 GCD/LCM 求和问题的通用且高效的高级技巧。