自动搬运

查看原文

来自洛谷，原作者为

	syzf2222 I am the most handsome man in the world,not one of them

搬运于2025-08-24 22:45:48，当前版本为作者最后更新于2023-03-12 19:33:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

注意到只有 $a>b>c$ 时，$(a,b,c)$ 的贡献才不为 $0$。

解法一：

根据调和级数，我们有：

$$\sum_{i=1}^n \dfrac{n}{i} = O(n\log n)$$

枚举 $b$ 和 $c$，再枚举 $s$ 表示 $a$ 是 $c$ 的几倍，这样满足条件的 $a$ 是一段区间，记为 $[L,R]$，于是我们需要计算：

$$\sum_{b=1}^n \sum_{c=b+1}^n \lfloor\dfrac{b}{c}\rfloor \sum_{s=1}^{n/c} s \sum_{a=L}^R \lfloor\dfrac{a}{b}\rfloor $$

对每个 $b$，使用前缀和预处理出 $\sum \lfloor\dfrac{i}{b}\rfloor$ ，即可消去最后一个求和符号。

如果暴力枚举 $b,c,s$，总复杂度为 $O(n^2\log n)$，可以通过此题。

解法二

我们有：

$$\sum_{i\geqslant 1}\frac{1}{i^2}=\frac{\pi^2}{6}$$

枚举 $a$，枚举 $b,c$ 分别是 $a$ 的几倍，我们需要求 $b\in[L_b,R_b],c\in[L_c,R_c]$ 的所有 $b,c$ 对的 $\lfloor\frac{b}{c}\rfloor$ 之和，我们可以预处理一个二维前缀和统计，于是时间复杂度为：

$$\sum_{i=1}^n(\frac ni)^2\leqslant n^2\sum_{i\geqslant 1}\frac{1}{i^2}=O(n^2) $$