P4900食堂

P4900 食堂

方案一 $O(n\sqrt n)$:

首先可以考虑一下这个小数部分该如何处理,显然是可以利用这个高斯函数的性质的:${p}=p-[p]$。

所以第 $n$ 行的和就可以写作:

所以后面那个可以整数分块,前面的 $O(n)$ 预处理,整体时间复杂度 $O(n\sqrt n)$,过不了的。

期望得分:$50$ 分

方案二 $O(n\log n)$

考虑这一行的分子理论上应该是上一行的分子 $+1$,所以理论上是可以直接继承的,但是分子的值域却只能是 $[0,n)$,所以要考虑剪去变成零的数的贡献,那么这个就应该是 $\sigma(i)$,就可以 $O(n\log n)$ 预处理了。

Code

方案三 $O(n)$

事实证明确实是可以 $O(n)$ 的,就是一个线性筛就可以了。

Code