前言
数论分块我实际上在2021年的暑假就已经接触过了，当时是当成了定理来记，所以现在忘得也差不多了。
最近决定重温（从零开始重修）数论分块，利用坐地铁的时间看了几篇关于数论分块的博客文章（源自《洛谷日报》），感觉有些讲得不是非常详细，质量参差不齐。有些往往只放几个性质，然后将结论直接写在下面。这种书写方式首先忽略了思维引导的过程，其次也没有将推导过程讲清楚。于是借此我也进行一些补充，把作为数论小白的理解心得写得稍微详细一些。
问题简化
求 \(\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor\)
性质
性质0
设 \(x,y\) 为任意实数。
显然，\(x\) 满足 \(\lfloor x \rfloor \leq x\)
显然，\(x,y\) 满足若\(x \leq y\)，则有 \(\lfloor x \rfloor \leq \lfloor y \rfloor\)
性质1
对于一个 \(i\) 满足 \(1 \leq i \leq n\)，则有且仅有一个包含 \(i\) 的连续区间 \([l,r]\) 满足对于其中任一整数 \(j\) 都有 \(\lfloor \frac{n}{i} \rfloor = \lfloor \frac{n}{j} \rfloor\)，这里记为一个同商块。
证：
分析 \(y = \frac{n}{x}\) 在正数部分的图像会发现这是一个反比例函数，性质显然。
性质2
对区间 \([1,n]\) 一定只存在 \(2 \sqrt{n}\) 或 \((2 \sqrt{n} - 1)\) 个不同且连续、长度递增的同商块。
证：
见此博客文章。
这是我几个月前在网上翻到的，真的写得挺好的。
此文章甚至提出了另一种解决此问题的方法，但这里不再说了。
性质3
\[\lfloor \frac{n}{i} \rfloor = \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \rfloor \]即 \(i\) 与 \(\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor\) 一定在同一个同商块中。
证：
\[\because \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \leq \frac{n}{\lfloor \frac{n}{i} \rfloor} \]\[\therefore \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \geq \frac{n}{\frac{n}{\lfloor \frac{n}{i} \rfloor}} \]\[\therefore \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \geq \lfloor \frac{n}{i} \rfloor \]\[\therefore \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \rfloor \geq \lfloor \frac{n}{i} \rfloor \]\[\because \lfloor \frac{n}{i} \rfloor \leq \frac{n}{i} \]\[\therefore \frac{n}{\lfloor \frac{n}{i} \rfloor} \geq \frac{n}{\frac{n}{i}} \]\[\therefore \frac{n}{\lfloor \frac{n}{i} \rfloor} \geq i \]\[\therefore \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \geq \lfloor i \rfloor \]\[\therefore \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \geq i \]\[\therefore \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \leq \frac{n}{i} \]\[\therefore \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \rfloor \leq \lfloor \frac{n}{i} \rfloor \]\[\because \begin{cases} \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \rfloor \geq \lfloor \frac{n}{i} \rfloor \\ \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \rfloor \leq \lfloor \frac{n}{i} \rfloor \\ \end{cases} \]\[\therefore \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor} \rfloor = \lfloor \frac{n}{i} \rfloor \]性质4
\[i \leq \frac{n}{\lfloor \frac{n}{i} \rfloor} \]即 $ \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor $ 一定是包含 \(i\) 的同商块的右端点。
证：
\[\because \lfloor \frac{n}{i} \rfloor \leq \frac{n}{i} \]\[\therefore \frac{n}{\lfloor \frac{n}{i} \rfloor} \geq \frac{n}{\frac{n}{i}} \]\[\therefore \frac{n}{\lfloor \frac{n}{i} \rfloor} \geq i \]\[\therefore \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \geq \lfloor i \rfloor \]\[\therefore \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \geq i \]\[\therefore i \leq \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \]具体实现
问题解决
由 \(i\) 到 \(\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor\) 的所有值除 \(n\) 并向下取整的结果一定是相等的（性质1、3、4），因此直接计算每个同商块的贡献，因为最多只有 \(2 \sqrt{n}\)
个不同的同商块（性质2），而对于任意一个 \(i\) 我们都直到它所在同商块的右端点，所以可以直接枚举每个同商块，每次使 \(i\) 变为 \(\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor + 1\)。
Code:
int Ans = 0;
for (int L = 1, R;L <= n;L = R + 1){
R = n / (n / L);
Ans = (Ans + (R - L + 1) * (n / L) % mod) % mod;
}
return Ans;
问题衍生
二维数论分块，感兴趣的可以自己去查，这里不说了。