P1829 [国家集训队] Crash的数字表格 / JZPTAB

拆拆拆：

\[\sum_{i=1}^n\sum_{j=1}^m \frac{ij}{(i,j)} \]

\[=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m[(i,j)=d]\frac{ij}{d} \]

\[=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}[(i,j)=1]ij \]

\[=\sum_{d=1}^{\min(n,m)}d\sum_{c=1}^{\lfloor \frac{\min(n,m)}{d}\rfloor}\mu(c)c^2\sum_{i=1}^{\lfloor \frac{n}{cd}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{cd}\rfloor}ij \]

\[=\sum_{d=1}^{\min(n,m)}d\sum_{c=1}^{\lfloor \frac{\min(n,m)}{d}\rfloor}\mu(c)c^2(\sum_{i=1}^{\lfloor \frac{n}{cd}\rfloor}i)(\sum_{j=1}^{\lfloor \frac{m}{cd}\rfloor}j) \]

\[=\sum_{d=1}^{\min(n,m)}d\sum_{c=1}^{\lfloor \frac{\min(n,m)}{d}\rfloor}\mu(c)c^2(\frac{(\lfloor \frac{n}{cd}\rfloor+1)\lfloor \frac{n}{cd}\rfloor}{2})(\frac{(\lfloor \frac{m}{cd}\rfloor+1)\lfloor \frac{m}{cd}\rfloor}{2}) \]

然后内层如果整除分块就是 \(O(n\ln\sqrt{n})\) 可以通过。