整除分块/数论分块

整除分块/数论分块

$O(\sqrt{N})$的时间复杂度内计算下列式子
$$\sum_{i=1}^N \lfloor{\frac{N}{i}}\rfloor$$

为了加速计算,我们需要计算对于一个固定的取值,有多少种$i$可以选择。

即对于一个$\lfloor{\frac{N}{i}}\rfloor$,要找到最大的$d$,使得$\lfloor{\frac{N}{i}}\rfloor = \lfloor{\frac{N}{i+d}}\rfloor$

不妨设$ki + p = N$,$k(i+d) + p’ = N$

那么有$p’ = p - kd$, 因为$p’ \geq 0$,因此$d \leq \lfloor{\frac{p}{k}}\rfloor$

那么$i + d_{max} = i + \lfloor{\frac{p}{k}}\rfloor = i + \lfloor{\frac{N - ki}{k}}\rfloor = \lfloor{\frac{N}{k}}\rfloor = \lfloor{\frac{N}{\lfloor{\frac{N}{i}}\rfloor}}\rfloor$

又因为$\lfloor{\frac{N}{i}}\rfloor$的取值不会超过$O(\sqrt{N})$种,因此时间复杂度可以控制在$O(\sqrt{N})$之内。

1
2
3
4
5
// O(sqrt(n))
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / i);
ans += (n / l) * (r - l + 1);
}