警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P1829」Crash 的数字表格 - 莫比乌斯反演

题意

传送门:洛谷 P1829 - Crash的数字表格 / JZPTAB

\(\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)\)\(n, m \le 10^7\)

解法

推柿子。

\[ \begin{aligned} & \text{suppose}~n\le m, \quad \operatorname{sum}(n,m) = \sum_{i=1}^n\sum_{j=1}^mi\cdot j=\frac{n(n+1)}2\cdot\frac{m(m+1)}2, \\ & \begin{aligned} & \sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j) \\ = & \sum_{i=1}^n\sum_{j=1}^m\frac{i\cdot j}{\gcd(i,j)} \\ = & \sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]i\cdot j \\ = & \sum_{d=1}^nd\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\frac md\right\rfloor}\varepsilon(\gcd(i,j))i\cdot j \\ = & \sum_{d=1}^nd\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\frac md\right\rfloor}\sum_{k\mid\gcd(i,j)}\mu(k)i\cdot j \\ = & \sum_{d=1}^nd\sum_{k=1}^{\left\lfloor\frac nd\right\rfloor}\mu(k)\sum_{k\mid i}^{\left\lfloor\frac nd\right\rfloor}\sum_{k\mid j}^{\left\lfloor\frac md\right\rfloor}i\cdot j \\ = & \sum_{d=1}^nd\sum_{k=1}^{\left\lfloor\frac nd\right\rfloor}\mu(k)k^2\sum_{i=1}^{\left\lfloor\frac n{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac m{dk}\right\rfloor}i\cdot j \\ = & \sum_{d=1}^nd\sum_{k=1}^{\left\lfloor\frac nd\right\rfloor}\mu(k)k^2\cdot\operatorname{sum}\!\left(\left\lfloor\frac n{dk}\right\rfloor,\left\lfloor\frac m{dk}\right\rfloor\right) \\ \end{aligned} \\ & \text{let}~f(x,y) = \sum_{k=1}^x\mu(k)k^2\cdot\operatorname{sum}\!\left(\left\lfloor\frac xk\right\rfloor,\left\lfloor\frac yk\right\rfloor\right), \\ & \text{so}~ans = \sum_{d=1}^nd\cdot f\!\left(\left\lfloor\frac nd\right\rfloor,\left\lfloor\frac md\right\rfloor\right). \end{aligned} \]

然后两次数论分块即可。复杂度 \(O(n)\)

代码