P1829 题解

· · 题解

本题我由于莫反不熟练，看了题解。

假设 n \le m。
求 \sum\limits_{i=1}^n\sum\limits_{j=1}^m lcm(i,j)。

转化：

\sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{ij}{(i,j)} $=\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor \frac{m}{d}\rfloor} \sum\limits_{k|(i,j)}\mu(k)\cdot ij

设 S(n,m) = \sum\limits_{i=1}^n\sum\limits_{j=1}^m \sum\limits_{k|(i,j)}\mu(k)\cdot ij。
则原答案变为 \sum\limits_{d=1}^n S(\lfloor \frac{n}{d}\rfloor,\lfloor \frac{m}{d}\rfloor)。
考虑如何求出 S(n,m)。

设 $T(n,m) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^m ij$。 则 $S(n,m) = \sum\limits_{k=1}^n \mu(k)S(\lfloor\frac{n}{d}\rfloor,\lfloor \frac{m}{d} \rfloor)$。 不难发现 $S(n,m)$ 可以在 $O(\sqrt n)$ 时间内整除分块解决。 同样， $\sum\limits_{d=1}^n S(\lfloor \frac{n}{d}\rfloor,\lfloor \frac{m}{d} \rfloor)$ 也可以用整除分块 $O(\sqrt n)$ 解决。 最后复杂度 $O(\sqrt n\cdot \sqrt n)=O(n)$。