题意简化

求满足以下条件的三元组 $(i,j,k)$ 数量：

• $1 \le i \le a$, $1 \le j \le b$, $1 \le k \le c$
• $\gcd(i,j)=\gcd(i,k)=\gcd(j,k)=1$

$a,b,c \le 50000$，模 $10^9+7$。

代码核心思路

1. 莫比乌斯反演

使用莫比乌斯函数 $\mu$ 处理互质条件。

2. 分情况计算

代码将答案分为三部分：

第一部分：$x=y=z$

即 $\gcd(i,j,k)$ 的共同因子 $d$。

$$\text{ans}_1 = \sum_{d=1}^{\min(a,b,c)} \mu(d) \cdot \lfloor \frac{a}{d} \rfloor \cdot \lfloor \frac{b}{d} \rfloor \cdot \lfloor \frac{c}{d} \rfloor $$

其中 $\mu(d)$ 的取值：

• $\mu(1)=1$
• $\mu(p_1 p_2 \dots p_k)=(-1)^k$（质因子各不同）
• 有平方因子时为 $0$

代码中将 $-1$ 存储为 $mod-1$。

第二部分：两个数相等，第三个数不同

即 $\gcd(i,j)=g_1$, $\gcd(i,k)=g_2$, $\gcd(j,k)=g_3$ 中有两个相等。

设 $L=\text{lcm}(x,y)$，其中 $x,y$ 是某两个 $\gcd$ 的值。

对于每个 $L$，枚举其因子 $x,y$（$x<y$ 且 $xy=L$），计算贡献：

• $x=y=z$ 已算过
• 两个相等，一个不同

贡献公式为：

$$\sum \mu(\cdot) \cdot \lfloor \frac{a}{\cdot} \rfloor \cdot \lfloor \frac{b}{\cdot} \rfloor \cdot \lfloor \frac{c}{\cdot} \rfloor $$

有 6 种对称情况。

第三部分：$x,y,z$ 两两不同

即 $\gcd(i,j)=x$, $\gcd(i,k)=y$, $\gcd(j,k)=z$ 互不相同。

需要找三元组 $(x,y,z)$ 满足：

• $x,y,z$ 是某些数的 $\gcd$
• $\text{lcm}(x,y)=A$, $\text{lcm}(y,z)=B$, $\text{lcm}(z,x)=C$ 存在对应关系

代码通过图枚举实现：

• 以 $x$ 为点
• 如果 $\text{lcm}(x,y)=L \le c$，则在 $x$ 和 $y$ 间连边，边权为 $L$
• 找三元环 $(x,y,z)$，计算贡献

3. 算法流程

1. 预处理（Init）：

   • 线性筛求 $\mu(1..50000)$
   • 预处理每个数的质因子列表 fac[i]

2. 排序（calc）：

   • 将 $a,b,c$ 排序使得 $a \le b \le c$

3. 三部分计算：

   • 第一部分：直接求和
   • 第二部分：枚举 $L$，用状压枚举因子对 $(x,y)$
   • 第三部分：建图找三元环

4. 三元环计数优化：

   • 按度数排序，只从度数小的点出发
   • 复杂度 $O(m\sqrt{m})$，$m$ 为边数

关键优化

1. 莫比乌斯函数预处理：线性筛 $O(n)$
2. 因子枚举：利用质因子列表状压枚举
3. 三元环计数：定向边技巧，避免 $O(n^3)$
4. 整除分块思想：用 a/L 等形式快速计算

复杂度分析

• 预处理：$O(n \log \log n)$
• 第一部分：$O(n)$
• 第二部分：$O(\sum_{L=1}^c 2^{\omega(L)})$，$\omega(L)$ 是 $L$ 的质因子数，实际很小
• 第三部分：$O(m\sqrt{m})$，边数 $m$ 不大

对于 $n=50000$ 可过。

代码特点

• 使用莫比乌斯反演处理互质条件
• 分三类情况讨论，避免重复计数
• 三元环计数用于处理最复杂情况
• 模运算优化：用减法代替取模