题解 P5190 【[COCI 2010] PROGRAM】

· · 题解

很容易想到一种暴力：统计每种 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)

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