整除分块（未完成）

userId_undefined
yanghongzheng
禁言
荣耀黄金USACO

2026-04-06 13:01:07

发布于：北京

38阅读
0回复
0点赞

算法讲解

首先我们先以问题：

给出一个 nn，求 ∑i=1n⌊ni⌋\sum_{i=1} ^{n} \lfloor \dfrac{n}{i} \rfloor。

引入。

我们以 n=91−78n = 91 - 78 为例。

上图为 f(x)=91−78xf(x) = \dfrac{91-78}{x} 的函数图像。

我们对此函数进行修改，添加题目中的向下取整：

上图为 f(x)=⌊91−78x⌋f(x) = \lfloor \dfrac{91-78}{x} \rfloor 的函数图像。

图像被分为了 91−7891 - 78 个部分，但有效的、会被取到的取值只有 66 个。

那么我们可以把这些包含整数的块取出来，一次性得出一个块的答案，把整块对答案的贡献加上即可。

那么怎么计算每个块的答案呢？

每个块都有一个头 ll 和尾 rr。设有 mm 个块，那么开始的问题可以被表示为 ∑i=1m(ri−li+1)⌊nli⌋\sum _{i = 1} ^m (r_i - l_i + 1) \lfloor \dfrac{n}{l_i} \rfloor。lil_i 显然可以被表示为 ri−1+1r_{i-1} + 1，所以只需要计算 rir_i 即可。

给出一个结论： 对于整数 ii，其所在块的右端点为 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor。

接下来我们来证明：

首先我们要证明 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor 与 ii 在同一块，也就是：

⌊n⌊n⌊ni⌋⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor= \lfloor\frac{n}{i}\rfloor

易证：

⌊x⌋≤x\lfloor x\rfloor \leq x

x≤y→⌊x⌋≤⌊y⌋x \le y\to \lfloor x\rfloor \le \lfloor y\rfloor

x≥y→⌊x⌋≥⌊y⌋x \ge y\to \lfloor x\rfloor \ge \lfloor y\rfloor

则：

⌊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

⌊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

所以：

⌊n⌊n⌊ni⌋⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor= \lfloor\frac{n}{i}\rfloor

我们还要证明：

i≤⌊n⌊ni⌋⌋i \le \lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor

也就是 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor 是这个块内最大的，即为块的右端点，这个很好证明：

⌊n⌊ni⌋⌋≥⌊nni⌋=i\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor\ge \lfloor\frac{n}{ \frac n i }\rfloor=i

这样我们就以代数方式证明了结论。

接下来证明一下复杂度：

在 [1,⌊n⌋][1, \lfloor \sqrt{n} \rfloor] 里，最多有 n\sqrt{n} 种取值。

在 (⌊n⌋,n](\lfloor \sqrt{n} \rfloor,n] 里，显然也有 n\sqrt{n} 种取值。

复杂度为 O(n)。O(\sqrt 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

userId_undefined
去预览
0/2000

全部评论 8

热门讨论