数论分块

作者: dachengquan | 来源:发表于2020-08-05 15:47 被阅读0次

余数之和
就是求解 $\sum _{i=1}^N \lfloor \frac {N}{i} \rfloor$
举例当N=10的时候，i为6,7,8,9， $\lfloor \frac {N}{i} \rfloor$ 的数都是1。
我们只要确定每一段的界限，就可以快速求和。
结论：假设每一段的左边界是x，那么右边界是 $\lfloor N / \lfloor {N}/{x} \rfloor \rfloor$
可以想象另一种模型，将N分为 $\lfloor {N}/{x} \rfloor+1$ 段前 $\lfloor {N}/{x} \rfloor$ 段长度固定，最后一段长度小于左边的每一段的长度，并且大于0。x是左边每一段的长度，我们就是让这个长度尽可能的大。也就是最后一段长度为0。把N均分给每一段， $\lfloor N / \lfloor {N}/{x} \rfloor \rfloor$ 因为x不能取小数，所以向下取整。