HDU6715 题解

· · 题解

本题仍然参照了其他题解，原因是最后一步没能转化为 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)) 这是关键的一步，令 $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)$。