【BZOJ2154】Crash的数字表格

$$\begin{align}
\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)&=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{(i,j)}\\
&=\sum_{d=1}^{min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]ijd\\
&=\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{p|i,p|j}\mu(p)ij\\
&=\sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}p^2\mu(p)\sum_{i=1}^{\lfloor\frac{n}{dp}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dp}\rfloor}ij\\
\end{align}$$

前半部分和后半部分的复杂度均为\(O(\sqrt{n})\),总复杂度\(O(n)\)。

说点什么

  Subscribe  
提醒