本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 16:10:13

本题仍然参照了其他题解，原因是最后一步没能转化为 dirichlet 卷积的形式。

假设 $n \le m$。

需要求解的：$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \mu(lcm(ij))$。

引理：$\mu(lcm(i,j))=\mu(i)\mu(j)\mu((i,j))$。
这个比较简单，我都能发现，较为显然不用证明。

原始转化为 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m \mu(i)\mu(j)\mu((i,j))$
$= \sum\limits_{d=1}^n \mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} \mu(id)\mu(jd)[(i,j)=1]$
$= \sum\limits_{d=1}^n \mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} (\mu(id)\mu(jd)\sum\limits_{k|(i,j)} \mu(k))$
$= \sum\limits_{d=1}^n\sum\limits_{k=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{i=1}^{\lfloor \frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{kd} \rfloor} \mu(d)\mu(k)\mu(ikd)\mu(jkd)$。

这是关键的一步，令 $T=kd$，此处的用意在于将前两个 sigma 转化为卷积的形式，并将后面的 $kd$ 合并为一个变量。

原式变为 $\sum\limits_{T=1}^n \sum\limits_{d|T}\mu(d)\mu(\frac{T}{d})\sum\limits_{i=1}^{\lfloor \frac{n}{T} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{T}\rfloor}\mu(iT)\mu(jT)$。

对于每个 $T$，$\sum\limits_{d|T}\mu(d)\mu(\frac{T}{d})$ 可以 $O(n\log n)$ 预处理，而 $\sum\limits_{i=1}^{\lfloor \frac{n}{T} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{T}\rfloor}\mu(iT)\mu(jT) = (\sum\limits_{i=1}^{\lfloor \frac{n}{T}\rfloor}\mu(iT))(\sum\limits_{j=1}^{\lfloor\frac{m}{T}\rfloor} \mu(jT))$，这个也可以暴力计算。

最后复杂度 $O(n \log n)$。