应用场景
求
\[\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\]
算法讲解
我们通过模拟可以很轻松的做到 \(\Theta(n)\) 的效率求解
但是事实上我们可以做到 \(\Theta(\sqrt{n})\) 的复杂度
我们发现对于 \(\lfloor\frac{n}{i}\rfloor\), 有许多值其实是一样的
然后我们发现对于每一个值相同的块, 它的最后一个数是 \(n/(n/i)\)
于是就可以在 \(\Theta(\sqrt{n})\) 的复杂度内求出答案啦
代码
- for (int l = 1, r; l <= n; l = r + 1){
- r = n / (n / l);
- ans += (r - l + 1) * (n / l);
- }
实际应用
在莫比乌斯函数等数论题中用于简化时间复杂度
[算法] 整除分块
来源: http://www.bubuko.com/infodetail-3098657.html