P9148 除法题 题解

· · 题解

注意到只有 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)