算法讲解
首先我们先以问题：
给出一个 n，求 ∑i=1n⌊in⌋。
引入。
我们以 n=91−78 为例。
上图为 f(x)=x91−78 的函数图像。
我们对此函数进行修改，添加题目中的向下取整：
上图为 f(x)=⌊x91−78⌋ 的函数图像。
图像被分为了 91−78 个部分，但有效的、会被取到的取值只有 6 个。
那么我们可以把这些包含整数的块取出来，一次性得出一个块的答案，把整块对答案的贡献加上即可。
那么怎么计算每个块的答案呢？
每个块都有一个头 l 和尾 r。设有 m 个块，那么开始的问题可以被表示为 ∑i=1m(ri−li+1)⌊lin⌋。li 显然可以被表示为 ri−1+1，所以只需要计算 ri 即可。
给出一个结论： 对于整数 i，其所在块的右端点为 ⌊⌊in⌋n⌋。
接下来我们来证明：
首先我们要证明 ⌊⌊in⌋n⌋ 与 i 在同一块，也就是：
⌊⌊⌊in⌋n⌋n⌋=⌊in⌋
易证：
⌊x⌋≤x
x≤y→⌊x⌋≤⌊y⌋
x≥y→⌊x⌋≥⌊y⌋
则：
⌊⌊⌊in⌋n⌋n⌋≥⌊⌊in⌋nn⌋=⌊in⌋
⌊⌊⌊in⌋n⌋n⌋≤⌊⌊inn⌋n⌋=⌊in⌋
所以：
⌊⌊⌊in⌋n⌋n⌋=⌊in⌋
我们还要证明：
i≤⌊⌊in⌋n⌋
也就是 ⌊⌊in⌋n⌋ 是这个块内最大的，即为块的右端点，这个很好证明：
⌊⌊in⌋n⌋≥⌊inn⌋=i
这样我们就以代数方式证明了结论。
接下来证明一下复杂度：
在 [1,⌊n⌋] 里，最多有 n 种取值。
在 (⌊n⌋,n] 里，显然也有 n 种取值。
复杂度为 O(n)。
引入题关键代码如下：
int r;
for(int l = 1;l <= n;l = r + 1){
r = n / (n / l);
ans += (r - l + 1) * (n / l);
}
例题
P15566
~
P2261
~
P3935
~
推荐练习题
AT_arc068_c、P13212、P4863
有帮助，赞一个