P10239 [yLCPC2024] G. 系ぎて

251Sec · 2024-03-09 20:03:10 · 题解

所求即为 \sum\limits_{i=1}^n \left\lfloor\dfrac{n}{i}\right\rfloor\sigma_0(i)，直接整除分块，那么需要求整除分块位置的 \sigma_0 前缀和，再套一层整除分块复杂度是 O(n^{\frac{3}{4}}) 的，本地跑了一下跑得飞快，交上去直接 T 飞了，这就是洛谷评测机给我的自信。那么我们直接把里层那个求 \sigma_0 前缀和的整除分块换成 DIVCNT1 那个 O(n^\frac{1}{3} \log n) 的做法，可以发现跑得飞快直接就过了。