自动搬运

查看原文

来自洛谷，原作者为

	Planet6174 **

搬运于2025-08-24 22:08:03，当前版本为作者最后更新于2019-01-08 16:15:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很容易想到一种暴力：统计每种 jump 的出现次数 cnt[jump]，然后

for (int jump = 1; jump <= N; ++jump)
  for (int i = 0; i < N; i += jump)
    seq[i] += cnt[jump];

你以为这东西的时间复杂度是 $O(N^2)$ 的，结果……你发现这个程序居然 AC 了。

原因很简单，还记得约数个数性质吗？

$O(N+\frac N 2+\frac N 3+\dots+\frac N N)=O(N\log N)$

最后吐槽一句，尽管这个题考点很正常，但个人觉得这题丢到考场上是会搞出负区分度的（