算法讲解
首先我们先以问题：
> 给出一个 nnn，求 ∑i=1n⌊ni⌋\sum_{i=1} ^{n} \lfloor \dfrac{n}{i} \rfloor∑i=1n ⌊in ⌋。
引入。
我们以 n=91−78n = 91 - 78n=91−78 为例。
上图为 f(x)=91−78xf(x) = \dfrac{91-78}{x}f(x)=x91−78 的函数图像。
我们对此函数进行修改，添加题目中的向下取整：
上图为 f(x)=⌊91−78x⌋f(x) = \lfloor \dfrac{91-78}{x} \rfloorf(x)=⌊x91−78 ⌋ 的函数图像。
图像被分为了 91−7891 - 7891−78 个部分，但有效的、会被取到的取值只有 666 个。
那么我们可以把这些包含整数的块取出来，一次性得出一个块的答案，把整块对答案的贡献加上即可。
那么怎么计算每个块的答案呢？
每个块都有一个头 lll 和尾 rrr。设有 mmm 个块，那么开始的问题可以被表示为 ∑i=1m(ri−li+1)⌊nli⌋\sum _{i = 1} ^m (r_i - l_i + 1) \lfloor \dfrac{n}{l_i} \rfloor∑i=1m (ri −li +1)⌊li n ⌋。lil_ili 显然可以被表示为 ri−1+1r_{i-1} + 1ri−1 +1，所以只需要计算 rir_iri 即可。
给出一个结论： 对于整数 iii，其所在块的右端点为 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor⌊⌊in ⌋n ⌋。
接下来我们来证明：
首先我们要证明 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor⌊⌊in ⌋n ⌋ 与 iii 在同一块，也就是：
⌊n⌊n⌊ni⌋⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor= \lfloor\frac{n}{i}\rfloor ⌊⌊⌊in ⌋n ⌋n ⌋=⌊in ⌋
易证：
⌊x⌋≤x\lfloor x\rfloor \leq x ⌊x⌋≤x
x≤y→⌊x⌋≤⌊y⌋x \le y\to \lfloor x\rfloor \le \lfloor y\rfloor x≤y→⌊x⌋≤⌊y⌋
x≥y→⌊x⌋≥⌊y⌋x \ge y\to \lfloor x\rfloor \ge \lfloor y\rfloor x≥y→⌊x⌋≥⌊y⌋
则：
⌊n⌊n⌊ni⌋⌋⌋≥⌊nn⌊ni⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor \ge \lfloor\frac{n}{\frac{n}{\lfloor \frac n i \rfloor}}\rfloor=\lfloor\frac{n}{i}\rfloor ⌊⌊⌊in ⌋n ⌋n ⌋≥⌊⌊in ⌋n n ⌋=⌊in ⌋
⌊n⌊n⌊ni⌋⌋⌋≤⌊n⌊nni⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor \le \lfloor\frac{n}{\lfloor\frac{n}{ \frac n i }\rfloor}\rfloor=\lfloor\frac{n}{i}\rfloor ⌊⌊⌊in ⌋n ⌋n ⌋≤⌊⌊in n ⌋n ⌋=⌊in ⌋
所以：
⌊n⌊n⌊ni⌋⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor= \lfloor\frac{n}{i}\rfloor ⌊⌊⌊in ⌋n ⌋n ⌋=⌊in ⌋
我们还要证明：
i≤⌊n⌊ni⌋⌋i \le \lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor i≤⌊⌊in ⌋n ⌋
也就是 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor⌊⌊in ⌋n ⌋ 是这个块内最大的，即为块的右端点，这个很好证明：
⌊n⌊ni⌋⌋≥⌊nni⌋=i\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor\ge \lfloor\frac{n}{ \frac n i }\rfloor=i ⌊⌊in ⌋n ⌋≥⌊in n ⌋=i
这样我们就以代数方式证明了结论。
接下来证明一下复杂度：
在 [1,⌊n⌋][1, \lfloor \sqrt{n} \rfloor][1,⌊n ⌋] 里，最多有 n\sqrt{n}n 种取值。
在 (⌊n⌋,n](\lfloor \sqrt{n} \rfloor,n](⌊n ⌋,n] 里，显然也有 n\sqrt{n}n 种取值。
复杂度为 O(n)。O(\sqrt n)。O(n )。
引入题关键代码如下：
例题
P15566
~
P2261
~
P3935
~
推荐练习题
AT_arc068_c、P13212、P4863
