洛谷：P2926：Patting Heads S

题目

P2926：Patting Heads S

分析

如果每一个数都要和其他数字比对然后计数，时间复杂度是\(O(n^2)\)。而题意中\(n\)最大是\(10^5\)，会超时。

从倍数的角度出发来看这个问题：

• 假定某个数i出现了c(ount)[i]次，
• 如果一个数j是i的倍数，
• 那么，j这个数一定会有c[i]次成为i的倍数。我们可以用另一个数组w(eight)来记录。
• 当然，最后要减去1，因为题目中明确说不算自己（而一个数肯定是自己的倍数）。

for(j=i;j<=...;j+=i) //j+=i保证j是i的倍数
{
  w[j]+=c[i]; //某个数i的出现次数c[i]，对j(这个i的倍数）来说，提供了c[i]次计数，换句话说，j能成为i的倍数的次数是c[i]
}

答案

思考

这个循环看似还是\(O(n^2)\)，因为内外循环都要从1跑到100,000。但我们内层循环的次数大大降低了，因为我们的步进速度是+=i。所以复杂度为\(O(\sum_{i=1}^n\frac{n}{i})=O(nlogn)\)，也称为“调和级数复杂度”。