不妨先设\(n<=m\)。
把题目的柿子推一下：
\[\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\]
由于\(lcm(i,j)*gcd(i,j)=ij\)
\[=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}\]
设\(d=gcd(i,j)\)，我们枚举\(d\)，提到最前面，再枚举\(i\)是\(d\)的几倍、\(j\)是\(d\)的几倍。
\[=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\frac{(d\times i)\times (d\times j)}{d}[gcd((d\times i),(d\times j))=d]\]
则在上面这个柿子中，\((d\times i)\)为原来的\(i\)，\((d\times j)\)为原来的\(j\)。将分式化简，\(gcd(d\times i,d\times j)=d\)里同时约掉一个\(d\)得：
\[=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}d\times i\times j[gcd(i,j)=1]\]
考虑到\(\sum_{i|n}\mu(i)=[n=1]\)，代入\([gcd(i,j)=1]\)得：
\[=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} i\times j\sum_{k|gcd(i,j)}\mu(k)\]
我们再次枚举\(k\)，提到\(\sum_{d=1}^n\)后：
\[=\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}i\times j[k|gcd(i,j)]\]
考虑到\([k|gcd(i,j)]\)即为\([k|i,k|j]\)：
\[=\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i[k|i]\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}j[k|j] \tag{1}\]
这时我们先推另一个柿子：\(\sum_{i=1}^n[k|i]\)，也就是询问\(1\)~\(n\)这些数中有多少个数是\(k\)的倍数，答案显然是\(\lfloor \frac{n}{k} \rfloor\)。
但如果是求\(\sum_{i=1}^ni[k|i]\)呢?
也就是吧所有\(1\)~\(n\)中所有是\(k\)的倍数的数加起来，答案显然就是\[1\times k+2\times k+...+\lfloor \frac{n}{k} \rfloor \times k=(1+2+...+\lfloor \frac{n}{k} \rfloor)\times k=\frac{(1+\lfloor \frac{n}{k} \rfloor)\times \lfloor \frac{n}{k} \rfloor \times k}{2}\]
把这个代入\((1)\)得
\[=\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\times\frac{(1+\lfloor \frac{\lfloor \frac{n}{d} \rfloor}{k} \rfloor)\times \lfloor \frac{\lfloor \frac{n}{d} \rfloor}{k} \rfloor \times k}{2}\times\frac{(1+\lfloor \frac{\lfloor \frac{m}{d} \rfloor}{k} \rfloor)\times \lfloor \frac{\lfloor \frac{m}{d} \rfloor}{k} \rfloor \times k}{2}\]
化简一下这个难看的柿子：
\[=\frac{1}{4}\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\times k^2\times(1+ \lfloor \frac{n}{dk} \rfloor)\times \lfloor \frac{n}{dk} \rfloor \times(1+ \lfloor \frac{m}{dk} \rfloor)\times \lfloor \frac{m}{dk} \rfloor\]
然后令\(T=dk\)，我们枚举\(T\)，并提到前面来。
\[\begin{aligned} & =\frac{1}{4}\sum_{T=1}^{n}(1+ \lfloor \frac{n}{T} \rfloor)\times \lfloor \frac{n}{T} \rfloor \times(1+ \lfloor \frac{m}{T} \rfloor)\times \lfloor \frac{m}{T} \rfloor\sum_{d|T}d\times\mu(\frac{T}{d})\times\frac{T^2}{d^2}\\ & =\frac{1}{4}\sum_{T=1}^{n}(1+ \lfloor \frac{n}{T} \rfloor)\times \lfloor \frac{n}{T} \rfloor \times(1+ \lfloor \frac{m}{T} \rfloor)\times \lfloor \frac{m}{T} \rfloor\sum_{d|T}\mu(\frac{T}{d})\times\frac{T^2}{d}\end{aligned}\]
令
\[f(T)=\sum_{T=1}^{n}(1+ \lfloor \frac{n}{T} \rfloor)\times \lfloor \frac{n}{T} \rfloor \times(1+ \lfloor \frac{m}{T} \rfloor)\times \lfloor \frac{m}{T} \rfloor\]
\[g(T)=\sum_{d|T}\mu(\frac{T}{d})\times\frac{T^2}{d}\]
那么显然，对于\(f(T)\)，我们可以用数论分块做出来。
而对于\(g(T)\)，由于\(\mu(\frac{T}{d})\)是积性函数，\(\frac{T^2}{d}\)是完全积性函数，所以\(g(T)\)也是积性函数。
那么对于\(g(T)\)，我们在线性筛时分三种情况讨论：
\(T=p\)，其中\(p\)为质数，那么我们再看回这个柿子：
\[g(T)=\sum_{d|T}\mu(\frac{T}{d})\times\f