题解：P10239 [yLCPC2024] G. 系ぎて

· · 题解

我们直接算贡献不好算，但是我们发现只要 ijk\le n 就能造成贡献，所以答案其实就是：

\sum_{i=1}^n \sum_{j=1}^{\lfloor \frac{n}i \rfloor}\lfloor \frac{n}{ij}\rfloor

然后设 f(n)=\sum_{i=1}^n\lfloor \frac{n}i \rfloor，这个东西可以用整除分块来做，然后原式等于 \sum_{i=1}^nf(\lfloor \frac{n}i \rfloor)，这时候可以再套一层整除分块。

以上其实是某篇题解的内容，当我学会了之后，高高兴兴的写出来，TLE……

似乎是我写的整除分块被卡常了，所以我采用了一种更好写也常数更小的整除分块（但是仅限 f(n)=\sum_{i=1}^n\lfloor \frac{n}i \rfloor 这个基本的式子）。

假设我们求出了 \sum_{i=1}^{\lfloor \sqrt n\rfloor}\lfloor \frac{n}i \rfloor 的答案，那么我们看这样一张图：

显然图像对于 y=x 这条直线是对称的，所以我们可以把刚才那个答案乘二，但是这样的话中间那个正方形算了两遍，所以要减去 (\lfloor \sqrt n\rfloor)^2。

这样虽然还是 O(\sqrt n) 的，但是没有被卡常（高兴）。