跳转至

# 数论分块

数论分块可以快速计算一些形如

𝑛∑𝑖=1 𝑓(𝑖)𝑔(⌊𝑛 𝑖⌋)∑i=1 n f(i)g(⌊n i⌋)

的和式．如果可以在 𝑂(1)O(1) 时间内计算出 ∑𝑟 𝑖=𝑙 𝑓(𝑖)∑i=l r f(i) 或已经预处理出 𝑓 f 的前缀和时，数论分块就可以在 𝑂(√𝑛)O(n) 时间内计算出上述和式的值．

数论分块常与 莫比乌斯反演 等技巧结合使用．

## 思路

首先，本文通过一个简单的例子来说明数论分块的思路．假设要计算如图所示的双曲线下的整点个数：

这相当于在计算和式：

1 1∑𝑖=1⌊1 1 𝑖⌋.∑i=1 11⌊11 i⌋.

这是前文所示和式在 𝑓(𝑘) =1, 𝑔(𝑘) =𝑘 f(k)=1, g(k)=k 时的特殊情况．

最简单的做法当然是逐列计算然后求和，但是这样需要计算第 𝑖 =1,2,⋯,1 1 i=1,2,⋯,11 列中每列整点的个数．观察图示可以发现，这些整点列的可以分成 5 5 块，每块内点列的高度是一致的，形成一个矩形点阵．所以，只要能够知道这些块的宽度，就能够通过计算这些矩形块的大小快速完成统计．

这就是整除分块的基本思路．

## 性质

本节讨论关于双曲线 𝑦 =𝑛 𝑥 y=n x 下整点分块的若干结论．具体地，需要将 1 ∼𝑛 1∼n 之间的整数按照 ⌊𝑛 𝑖⌋⌊n i⌋ 的取值分为若干块．设

𝐷(𝑛)={⌊𝑛 𝑖⌋:1≤𝑖≤𝑛, 𝑖∈𝐍+}.D(n)={⌊n i⌋:1≤i≤n, i∈N+}.

这就是 ⌊𝑛 𝑖⌋⌊n i⌋ 所有可能的取值集合．

首先，这样的不同取值只有 𝑂(√𝑛)O(n) 个．所以，数论分块得到的块的数目只有 𝑂(√𝑛)O(n) 个．

性质 1

|𝐷(𝑛)| ≤2√𝑛|D(n)|≤2 n．

证明

分两种情况讨论：

- 当 𝑖 ≤√𝑛 i≤n 时，𝑖 i 的取值至多 √𝑛 n 个，所以 ⌊𝑛 𝑖⌋⌊n i⌋ 的取值也至多只有 √𝑛 n 个．
- 当 𝑖 >√𝑛 i>n 时，⌊𝑛 𝑖⌋ ≤𝑛 𝑖 <√𝑛⌊n i⌋≤n i<n 也至多只有 √𝑛 n 个取值．

因此，所有可能取值的总数 |𝐷(𝑛)| ≤2√𝑛|D(n)|≤2 n．

通过更细致的分析，实际上可以精确地描述集合 𝐷(𝑛)D(n) 及其大小．

性质 2

设 𝑠 =⌊√𝑛⌋s=⌊n⌋．集合 𝐷(𝑛)D(n) 中的元素从小到大依次是

1<2<⋯<𝑠−1<𝑠≤⌊𝑛 𝑠⌋<⌊𝑛 𝑠−1⌋<⋯<⌊𝑛 2⌋<⌊𝑛 1⌋=𝑛.1<2<⋯<s−1<s≤⌊n s⌋<⌊n s−1⌋<⋯<⌊n 2⌋<⌊n 1⌋=n.

进而，|𝐷(𝑛)| =⌊√4 𝑛+1⌋ −1|D(n)|=⌊4 n+1⌋−1．

证明

首先，对于 1 ≤𝑖 ≤𝑠 1≤i≤s，可以证明 ⌊𝑛⌊𝑛/𝑖⌋⌋ =𝑖⌊n⌊n/i⌋⌋=i．令 𝑑 =⌊𝑛 𝑖⌋d=⌊n i⌋，需要证明 ⌊𝑛 𝑑⌋ =𝑖⌊n d⌋=i．写成不等式，这相当于已知 𝑑 ≤𝑛 𝑖 <𝑑 +1 d≤n i<d+1，需要证明 𝑖 ≤𝑛 𝑑 <𝑖 +1 i≤n d<i+1．已知条件可以写作 𝑖 ≤𝑛 𝑑 <𝑖 +𝑖 𝑑 i≤n d<i+i d，因此，只需要证明 𝑖 𝑑 ≤1 i d≤1，亦即 𝑖 ≤𝑑 =⌊𝑛 𝑖⌋i≤d=⌊n i⌋．这等价于 𝑖 ≤𝑛 𝑖 i≤n i，这对于所有 1 ≤𝑖 ≤𝑠 ≤√𝑛 1≤i≤s≤n 都成立．

这一结果实际上说明，映射 𝑖 ↦⌊𝑛 𝑖⌋i↦⌊n i⌋ 构成集合 {𝑖 :1 ≤𝑖 ≤𝑠}{i:1≤i≤s} 和集合 {⌊𝑛 𝑖⌋:1≤𝑖≤𝑠}{⌊n i⌋:1≤i≤s} 之间的双射．由于 𝑖 i 各不相同，⌊𝑛 𝑖⌋⌊n i⌋ 也各不相同．两个集合唯一有可能相同的元素就是 𝑠 s 与 ⌊𝑛 𝑠⌋⌊n s⌋．所以，|𝐷(𝑛)| =2 𝑠 −[𝑠=⌊𝑛/𝑠⌋]|D(n)|=2 s−[s=⌊n/s⌋]．

要得到 |𝐷(𝑛)||D(n)| 最终的表达式，需要考察何时 𝑠 =⌊𝑛 𝑠⌋s=⌊n s⌋ 成立．

- 当 𝑠 =⌊𝑛 𝑠⌋s=⌊n s⌋ 时，总有 𝑠 ≤𝑛 𝑠 <𝑠 +1 s≤n s<s+1，亦即 𝑠 2 ≤𝑛 <𝑠 2 +𝑠 s 2≤n<s 2+s．此时，有 4 𝑠 2 +1 ≤4 𝑛 +1 <4 𝑠 2 +4 𝑠 +1 =(2 𝑠 +1)2 4 s 2+1≤4 n+1<4 s 2+4 s+1=(2 s+1)2．又因为 4 𝑛 +1 4 n+1 一定是奇数，左侧可以等价地松弛到 4 𝑠 2 4 s 2，所以该条件就等价于 2 𝑠 ≤√4 𝑛+1 <2 𝑠 +1 2 s≤4 n+1<2 s+1，亦即 ⌊√4 𝑛+1⌋ =2 𝑠⌊4 n+1⌋=2 s．
- 当 𝑠 <⌊𝑛 𝑠⌋s<⌊n s⌋ 时，总有 𝑠 +1 ≤𝑛 𝑠 s+1≤n s，亦即 𝑠 2 +𝑠 ≤𝑛 s 2+s≤n．又因为 𝑛 <(𝑠 +1)2 n<(s+1)2，就有 𝑠 2 +𝑠 ≤𝑛 <(𝑠 +1)2 s 2+s≤n<(s+1)2．这就等价于 (2 𝑠 +1)2 ≤4 𝑛 +1 <4(𝑠 +1)2 +1(2 s+1)2≤4 n+1<4(s+1)2+1．再次利用 4 𝑛 +1 4 n+1 是奇数这一点，右侧可以等价地收紧到 4(𝑠 +1)2 4(s+1)2，所以该条件就等价于 2 𝑠 +1 ≤√4 𝑛+1 <2 𝑠 +2 2 s+1≤4 n+1<2 s+2，亦即 ⌊√4 𝑛+1⌋ =2 𝑠 +1⌊4 n+1⌋=2 s+1．

总结这两种情形，就得到 |𝐷(𝑛)| =⌊√4 𝑛+1⌋ −1|D(n)|=⌊4 n+1⌋−1 成立．

然后，单个块的左右端点都很容易确定．

性质 3

对于 𝑑 ∈𝐷(𝑛)d∈D(n)，所有满足 ⌊𝑛 𝑖⌋ =𝑑⌊n i⌋=d 的整数 𝑖 i 的取值范围为

⌊𝑛 𝑑+1⌋+1≤𝑖≤⌊𝑛 𝑑⌋.⌊n d+1⌋+1≤i≤⌊n d⌋.
证明

因为 ⌊𝑛 𝑖⌋ =𝑑⌊n i⌋=d 相当于不等式

𝑑≤𝑛 𝑖<𝑑+1.d≤n i<d+1.

这进一步等价于

𝑛 𝑑+1<𝑖≤𝑛 𝑑.n d+1<i≤n d.

利用 𝑖 ∈𝐍+i∈N+ 这一点，可以对该不等式取整，它就等价于

⌊𝑛 𝑑+1⌋+1≤𝑖≤⌊𝑛 𝑑⌋.⌊n d+1⌋+1≤i≤⌊n d⌋.

这一性质还体现了图像的对称性：每个块的右端点（前文图中的绿点）的集合恰为 𝐷(𝑛)D(n)．这很容易理解，因为整个图像关于直线 𝑦 =𝑥 y=x 是对称的．

除了这些性质外，集合 𝐷(𝑛)D(n) 还具有良好的递归性质：

性质 4

对于 𝑚 ∈𝐷(𝑛)m∈D(n)，有 𝐷(𝑚) ⊆𝐷(𝑛)D(m)⊆D(n)．

证明

设 𝑚 =⌊𝑛 𝑘⌋m=⌊n k⌋，那么，因为对于所有 𝑖 ∈𝐍+i∈N+，都有

⌊𝑚 𝑖⌋=⌊⌊𝑛/𝑘⌋𝑖⌋=⌊𝑛 𝑘 𝑖⌋∈𝐷(𝑛),⌊m i⌋=⌊⌊n/k⌋i⌋=⌊n k i⌋∈D(n),

所以，𝐷(𝑚) ⊆𝐷(𝑛)D(m)⊆D(n)．其中，第二个等号用到了 取整函数 关于嵌套分式的性质．

前文已经提到，𝐷(𝑛)D(n) 既是每块中 ⌊𝑛 𝑖⌋⌊n i⌋ 的取值集合，也是每块的右端点集合．这意味着，如果要递归地应用数论分块（即函数在 𝑛 n 处的值依赖于它在 𝑚 ∈𝐷(𝑛) ∖{𝑛}m∈D(n)∖{n} 处的值），那么在整个计算过程中所涉及的取值集合和右端点集合，其实都是 𝐷(𝑛)D(n)．一个典型的例子是 杜教筛．

## 过程

利用上一节叙述的结论，就得到数论分块的具体过程．

为计算和式

𝑛∑𝑖=1 𝑓(𝑖)𝑔(⌊𝑛 𝑖⌋)∑i=1 n f(i)g(⌊n i⌋)

的取值，可以依据 ⌊𝑛 𝑖⌋⌊n i⌋ 的取值将标号 𝑖 =1,2,⋯,𝑛 i=1,2,⋯,n 分块．因为 ⌊𝑛 𝑖⌋⌊n i⌋ 取值相同的标号是一段连续整数 [𝑙,𝑟][l,r]，所以该块中和式的取值为

(𝑟∑𝑖=𝑙 𝑓(𝑖))⋅𝑔(⌊𝑛 𝑙⌋).(∑i=l r f(i))⋅g(⌊n l⌋).

为了快速计算该和式，通常需要能够快速计算左侧关于 𝑓 f 的和式．有些时候，该和式的表达式是已知的，可以在 𝑂(1)O(1) 时间内完成单次计算；有些时候，可以预处理出它的前缀和，仍然可以在 𝑂(1)O(1) 时间内完成单次查询．

在顺次计算每块左右端点时，当前块的左端点 𝑙 l 就等于前一块的右端点再加 1 1，而当前块的右端点就等于 ⌊𝑛⌊𝑛/𝑙⌋⌋⌊n⌊n/l⌋⌋．由此，可以得到如下伪代码：

𝐀 𝐥 𝐠 𝐨 𝐫 𝐢 𝐭 𝐡 𝐦 S u m(𝑓,𝑔,𝑛):𝐈 𝐧 𝐩 𝐮 𝐭. 𝑛, 𝑠(𝑘)=∑𝑘 𝑖=1 𝑓(𝑘), 𝑔(𝑘).𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. 𝑆(𝑛)=∑𝑛 𝑖=1 𝑓(𝑖)𝑔(⌊𝑛/𝑖⌋).𝐌 𝐞 𝐭 𝐡 𝐨 𝐝.1 𝑙←1 2 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡←0 3 𝐰 𝐡 𝐢 𝐥 𝐞 𝑙≤𝑛 𝐝 𝐨 4 𝑟←⌊𝑛⌊𝑛/𝑙⌋⌋5 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡←𝑟 𝑒 𝑠 𝑢 𝑙 𝑡+(𝑠(𝑟)−𝑠(𝑙−1))⋅𝑔(⌊𝑛 𝑙⌋)6 𝑙←𝑟+1 7 𝐞 𝐧 𝐝 𝐰 𝐡 𝐢 𝐥 𝐞 8 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡 Algorithm Sum(f,g,n):Input. n, s(k)=∑i=1 k f(k), g(k).Output. S(n)=∑i=1 n f(i)g(⌊n/i⌋).Method.1 l←1 2 result←0 3 while l≤n do 4 r←⌊n⌊n/l⌋⌋5 result←result+(s(r)−s(l−1))⋅g(⌊n l⌋)6 l←r+1 7 end while 8 return result

假设单次计算 𝑠( ⋅)s(⋅) 的时间复杂度为 𝑂(1)O(1)，则整个过程的时间复杂度为 𝑂(√𝑛)O(n)．

## 扩展

前文讨论的是数论分块的最常见也最基本的形式．本节进一步讨论数论分块的扩展形式．

### 向上取整的数论分块

数论分块可以用于计算含有向上取整的和式：

𝑛∑𝑖=1 𝑓(𝑖)𝑔(⌈𝑛 𝑖⌉).∑i=1 n f(i)g(⌈n i⌉).

因为 ⌈𝑛 𝑖⌉ =⌊𝑛−1 𝑖⌋ +1⌈n i⌉=⌊n−1 i⌋+1，该和式可以转化为向下取整的情形：

𝑓(𝑛)𝑔(1)+𝑛−1∑𝑖=1 𝑓(𝑖)𝑔(⌊𝑛−1 𝑖⌋+1).f(n)g(1)+∑i=1 n−1 f(i)g(⌊n−1 i⌋+1).

注意到求和的上限发生了变化，以及 𝑖 =𝑛 i=n 时单独的一项．

### 多维数论分块

数论分块还可以用于处理包含不只有一个取整式的和式：

𝑛∑𝑖=1 𝑓(𝑖)𝑔(⌊𝑛 1 𝑖⌋,⌊𝑛 2 𝑖⌋,⋯,⌊𝑛 𝑚 𝑖⌋).∑i=1 n f(i)g(⌊n 1 i⌋,⌊n 2 i⌋,⋯,⌊n m i⌋).

为了应用数论分块的思想，需要保证每块中所有取整式 ⌊𝑛 1 𝑖⌋,⌊𝑛 2 𝑖⌋,⋯,⌊𝑛 𝑚 𝑖⌋⌊n 1 i⌋,⌊n 2 i⌋,⋯,⌊n m i⌋ 的取值都不发生变化，也就是说，多维的块应当是所有一维的块的交集．为此，对于已知的左端点 𝑙 l，相应的右端点为

m i n{⌊𝑛 1⌊𝑛 1/𝑙⌋⌋,⌊𝑛 2⌊𝑛 2/𝑙⌋⌋,⋯,⌊𝑛 𝑚⌊𝑛 𝑚/𝑙⌋⌋}.min{⌊n 1⌊n 1/l⌋⌋,⌊n 2⌊n 2/l⌋⌋,⋯,⌊n m⌊n m/l⌋⌋}.

也就是说，对于所有一维分块的右端点取最小值，作为多维分块的右端点．可以借助下图理解：

较为常见的是二维形式，此时可将前述伪代码中 𝑟 ←⌊𝑛⌊𝑛/𝑙⌋⌋r←⌊n⌊n/l⌋⌋ 替换成

𝑟←m i n{⌊𝑛 1⌊𝑛 1/𝑙⌋⌋,⌊𝑛 2⌊𝑛 2/𝑙⌋⌋}.r←min{⌊n 1⌊n 1/l⌋⌋,⌊n 2⌊n 2/l⌋⌋}.

### 任意指数数论分块

数论分块可以用于含有任意指数的取整式的和式计算：

⌊𝑛 𝛼/𝛽⌋∑𝑖=1 𝑓(𝑖)𝑔(⌊𝑛 𝛼 𝑖 𝛽⌋).∑i=1⌊n α/β⌋f(i)g(⌊n α i β⌋).

其中，𝛼,𝛽 α,β 为正实数．本文讨论的基本形式中，𝛼 =𝛽 =1 α=β=1．

性质

对于正整数 𝑛 n 和正实数 𝛼,𝛽 α,β，设

𝐷(𝑛,𝛼,𝛽)={⌊𝑛 𝛼 𝑖 𝛽⌋:𝑖=1,2,⋯,⌊𝑛 𝛼/𝛽⌋}.D(n,α,β)={⌊n α i β⌋:i=1,2,⋯,⌊n α/β⌋}.

那么，有

1. |𝐷(𝑛,𝛼,𝛽)| ≤2 𝑛 𝛼/(1+𝛽)|D(n,α,β)|≤2 n α/(1+β)．

2. 对于 𝑑 ∈𝐷(𝑛,𝛼,𝛽)d∈D(n,α,β)，使得 ⌊𝑛 𝛼 𝑖 𝛽⌋ =𝑑⌊n α i β⌋=d 成立的 𝑖 i 的取值范围为

   ⌊𝑛 𝛼/𝛽(𝑑+1)1/𝛽⌋+1≤𝑖≤⌊𝑛 𝛼/𝛽 𝑑 1/𝛽⌋.⌊n α/β(d+1)1/β⌋+1≤i≤⌊n α/β d 1/β⌋.

证明

对于第一点，分两种情况：

- 当 𝑖 ≤𝑛 𝛼 𝑖 𝛽 i≤n α i β 时，有 𝑖 ≤𝑛 𝛼/(1+𝛽)i≤n α/(1+β)，所以 ⌊𝑛 𝛼 𝑖 𝛽⌋⌊n α i β⌋ 至多有 𝑛 𝛼/(1+𝛽)n α/(1+β) 种取值．
- 当 𝑖 >𝑛 𝛼 𝑖 𝛽 i>n α i β 时，有 𝑖 >𝑛 𝛼/(1+𝛽)i>n α/(1+β)，进而有 𝑛 𝛼 𝑖 𝛽 <𝑛 𝛼/(1+𝛽)n α i β<n α/(1+β)，所以 ⌊𝑛 𝛼 𝑖 𝛽⌋⌊n α i β⌋ 也至多只有 𝑛 𝛼/(1+𝛽)n α/(1+β) 种取值．

综合两种情形，就有 |𝐷(𝑛,𝛼,𝛽)| ≤2 𝑛 𝛼/(1+𝛽)|D(n,α,β)|≤2 n α/(1+β)．

对于第二点，⌊𝑛 𝛼 𝑖 𝛽⌋ =𝑑⌊n α i β⌋=d 就等价于

𝑑≤𝑛 𝛼 𝑖 𝛽<𝑑+1⟺𝑛 𝛼/𝛽(𝑑+1)1/𝛽<𝑖≤𝑛 𝛼/𝛽 𝑑 1/𝛽.d≤n α i β<d+1⟺n α/β(d+1)1/β<i≤n α/β d 1/β.

对该不等式取整，就得到第二个命题．

利用这些性质，就可以在 𝑂(𝑛 𝛼/(1+𝛽))O(n α/(1+β)) 的时间复杂度下实现对任意指数的数论分块．

例子

例如，对于 𝛼 =𝛽 =1/2 α=β=1/2 时的如下和式

𝑛∑𝑖=1 𝑓(𝑖)𝑔(⌊√𝑛 𝑖⌋),∑i=1 n f(i)g(⌊n i⌋),

可以通过数论分块在 𝑂(𝑛 1/3)O(n 1/3) 时间内解决．已知块的左端点为 𝑙 l 时，可以计算右端点为 𝑟 =⌊𝑛⌊√𝑛/𝑙⌋2⌋r=⌊n⌊n/l⌋2⌋．

## 例题

UVa11526 H(n)

𝑇 T 组数据，每组一个整数 𝑛 n．对于每组数据，输出 ∑𝑛 𝑖=1⌊𝑛 𝑖⌋∑i=1 n⌊n i⌋．

解答

根据前文分析，可以对于每一块相同的 ⌊𝑛 𝑖⌋⌊n i⌋ 一起计算．时间复杂度为 𝑂(𝑇√𝑛)O(T n)．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include <iostream>

    long long H(int n) {
      long long res = 0;  // 储存结果
      int l = 1, r;       // 块左端点与右端点
      while (l <= n) {
        r = n / (n / l);  // 计算当前块的右端点
        // 累加这一块的贡献到结果中。乘上 1LL 防止溢出
        res += 1LL * (r - l + 1) * (n / l);
        l = r + 1;  // 左端点移到下一块
      }
      return res;
    }

    int main() {
      std::ios::sync_with_stdio(false);
      std::cin.tie(nullptr);
      int t, n;
      std::cin >> t;
      while (t--) {
        std::cin >> n;
        std::cout << H(n) << '\n';
      }
      return 0;
    }

Codeforces 1954E Chain Reaction

有一排 𝑛 n 只怪兽，每只怪兽初始血量为 𝑎 𝑖 a i．一次攻击会使一段连续的存活的怪兽血量减 𝑘 k，血量不大于 0 0 视作死亡．对于所有 𝑘 k 求出击杀所有怪兽所需攻击次数．其中，𝑛,𝑎 𝑖 ≤1 0 5 n,a i≤10 5．

解答

令 𝑎 0 =0 a 0=0．假设击杀所有前 (𝑖 −1)(i−1) 只怪兽需要 𝑇(𝑘,𝑖 −1)T(k,i−1) 次攻击，第 𝑖 i 只怪兽的血量为 𝑎 𝑖 a i．由于击杀第 (𝑖 −1)(i−1) 只怪兽时，需要攻击它 ⌈𝑎 𝑖−1/𝑘⌉⌈a i−1/k⌉ 次，这些攻击都可以延伸到第 𝑖 i 只怪兽．因此，要击杀第 𝑖 i 只怪兽，只需要再攻击 m a x{0,⌈𝑎 𝑖/𝑘⌉ −⌈𝑎 𝑖−1/𝑘⌉}max{0,⌈a i/k⌉−⌈a i−1/k⌉} 次．由此，总的攻击次数为

𝑇(𝑘,𝑛)=𝑛∑𝑖=1 m a x(0,⌈𝑎 𝑖 𝑘⌉−⌈𝑎 𝑖−1 𝑘⌉).T(k,n)=∑i=1 n max(0,⌈a i k⌉−⌈a i−1 k⌉).

由于题目涉及的 𝑛,𝑘 n,k 都比较大，对每个 𝑘 k 分别计算该和式并不可行．可以考虑对每个 𝑖 =1,2,⋯,𝑛 i=1,2,⋯,n，都维护数列 {𝑇(𝑘,𝑖)}𝑘{T(k,i)}k．初始时，设 𝑇(𝑘,0) ≡0 T(k,0)≡0．假设数列 {𝑇(𝑘,𝑖 −1)}𝑘{T(k,i−1)}k 已知，考虑如何对它进行修改才能得到数列 {𝑇(𝑘,𝑖)}𝑘{T(k,i)}k．根据前文分析，只需要对数列的第 𝑘 k 项增加 m a x(0,⌈𝑎 𝑖 𝑘⌉−⌈𝑎 𝑖−1 𝑘⌉)max(0,⌈a i k⌉−⌈a i−1 k⌉) 即可．利用二维数论分块，可以将这一修改操作拆分成 𝑂(√𝑎 𝑖−1 +√𝑎 𝑖)O(a i−1+a i) 段区间修改操作，且每段区间上增加的值是固定的．最后得到的数列 {𝑇(𝑘,𝑛)}𝑘{T(k,n)}k 就是答案．

由于题目涉及一系列区间加操作，且查询只发生所有修改完成后．所以，可以通过维护差分序列进行区间加修改，最后通过求前缀和得到所求数列．总的时间复杂度为 𝑂(∑√𝑎 𝑖)O(∑a i)．本题也存在其他解法．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include <algorithm>
    #include <iostream>

    constexpr int N = 100009;
    int n, a[N], maxn;
    long long ans[N];

    int main() {
      std::ios::sync_with_stdio(false);
      std::cin.tie(nullptr);
      std::cin >> n;
      for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        maxn = std::max(maxn, a[i]);
      }
      for (int i = 0; i < n; ++i)
        for (int l = 1, r;; l = r + 1) {
          r = std::min(l < a[i] ? (a[i] - 1) / ((a[i] - 1) / l) : N,
                       l < a[i + 1] ? (a[i + 1] - 1) / ((a[i + 1] - 1) / l)
                                    : N);  // 二维数论分块
          if (r == N) break;
          int x = (a[i + 1] - 1) / l - std::max(a[i] - 1, 0) / l;
          if (x > 0) ans[l] += x, ans[r + 1] -= x;  // 累加贡献
        }
      ++ans[0];  // ⌈a/l⌉=(a-1)/l+1的式子当a=0时不成立，需要修正
      for (int i = 1; i <= maxn; ++i)
        std::cout << (ans[i] += ans[i - 1]) << " \n"[i == maxn];
      return 0;
    }

## 习题

- UVa11526 H(n)
- Luogu P2261 CQOI2007 余数求和
- Luogu P3455 POI2007 ZAP-Queries

## 参考资料与注释

- 杜教筛的时空复杂度分析 by riteme

> 本页面最近更新：2025/11/1 21:29:33，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：c-forrest, Tiphereth-A, Xeonacid, yusancky, 2044-space-elevator, 383494, 99-woods, Backl1ght, caijianhong, CCXXXI, ghszt0, Great-designer, iamtwz, ksyx, Marcythm, qwqAutomaton, sshwy, StudyingFather, tder6, TOMWT-qwq
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用