警告

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

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

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

点击屏幕以关闭。

「SDOI 2015」约数个数和 - 莫比乌斯反演 + 结论

题意

传送门:洛谷 P3327 - 约数个数和

\(T\) 次询问,每次给 \(n, m\),询问 \(\sum_{i=1}^n\sum_{i=1}^m\operatorname{d}(i\cdot j)\)

\(T, n, m \le 4 \times 10^5\)

解法

惯例,推式子。

\[ \begin{aligned} & \begin{aligned} & \operatorname{d}(i\cdot j) \\ = & \sum_{x|i}\sum_{y|j}[\gcd(x,y)=1] \qquad(\text{神仙结论,证明咕咕}) \end{aligned} \\ & \begin{aligned} & \sum_{i=1}^n\sum_{j=1}^m\operatorname{d}(i\cdot j) \\ = & \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1] \\ = & \sum_{i=1}^n\sum_{j=1}^m\left\lfloor\frac ni\right\rfloor\!\left\lfloor\frac mj\right\rfloor\![\gcd(i,j)=1] \\ \end{aligned} \\ & \text{suppose}~f(x)=\sum_{i=1}^n\sum_{j=1}^m\left\lfloor\frac ni\right\rfloor\!\left\lfloor\frac mj\right\rfloor\![\gcd(i,j)=x], \\ & \quad F(x) = \sum_{x|d}f(d) = \sum_{i=1}^n\sum_{j=1}^m\left\lfloor\frac ni\right\rfloor\!\left\lfloor\frac mj\right\rfloor\![x|\gcd(i,j)] \\ & \text{so}~F(x) = \sum_{i=1}^{\lfloor n/x\rfloor}\sum_{j=1}^{\lfloor m/x\rfloor}\left\lfloor\frac n{ix}\right\rfloor\!\left\lfloor\frac m{jx}\right\rfloor, \\ & \begin{aligned} ans = & f(1) = \sum_{d=1}^n\mu(d)F(d) \\ = & \sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}\left\lfloor\frac n{id}\right\rfloor\!\left\lfloor\frac m{jd}\right\rfloor \\ = & \sum_{d=1}^n\mu(d)\left(\sum_{i=1}^{\lfloor n/x\rfloor}\left\lfloor\frac n{ix}\right\rfloor\right)\left(\sum_{j=1}^{\lfloor m/x\rfloor}\left\lfloor\frac m{jx}\right\rfloor\right) \\ \end{aligned} \\ & \text{suppose}~S(n) = \sum_{i=1}^n\left\lfloor\frac ni\right\rfloor = \sum_{i=1}^n\operatorname{d}(i), \\ & \text{obviusly}~ans = \sum_{d=1}^n\mu(d)S\!\left(\left\lfloor\frac nd\right\rfloor\right)\!S\!\left(\left\lfloor\frac md\right\rfloor\right). \end{aligned} \]

然后筛出 \(\mu, \operatorname{d}\),就可以用数论分块 \(O(\sqrt n)\) 做了。

代码