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

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

假设 $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} ij[(i,j)=1]$。
$=\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)$。
$S(n,m) = \sum\limits_{k=1}^n\mu(k)k^2 \sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij$。

设 $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)$。