数论分块

前言

这几天在学莫比乌斯反演的时候看到了关于数论分块的内容，写篇博客来记录一下相关的内容

整除分块

整除分块是用来计算形如 $sum_{i=1}^{n} lfloor frac{n}{i} floor$ 的式子的一种方法，当数据范围偏大时，显然 $O(n)$ 的算法会超时，那么就要用到整除分块的方法来进行计算。

首先我们可以打表观察一下，$lfloor frac{n}{i} floor$ 的值在一段连续的区间内是相同的，也就是说 $lfloor frac{n}{i} floor$ 的值呈块状分布。

并且我们可以得出，当 $i leq sqrt{n}$ 时，$lfloor frac{n}{i} floor$ 最多有 $sqrt{n}$ 种可能，同理可得当 $i>sqrt{n}$ 时，最多也只有 $sqrt{n}$ 种可能，所以我们可以在 $O(sqrt{n})$ 的复杂度内计算出该式子的值。

接下来便是寻找每一个 $lfloor frac{n}{i} floor$ 值所对应的连续区间，我们假设区间左端点为 $l$ ，那么区间的右端点便为 $lfloor frac{n}{lfloor frac{n}{l} floor} floor$。

证明：

我们假设 $lfloor frac{n}{l} floor = T$

则有 $n = l * T + x$ ，其中 $0 leq x < l$

下面寻找区间右端点，我们可以假设 $lfloor frac{n}{l + d} floor = T$

可得 $n = (l + d) * T + x'$，其中 $0 leq x' < l + d$

将两等式相减可得 $d = frac{x - x'}{T}$

因为我们要寻找区间右端点，所以我们需要 $d_{max}$

由上式可得出 $d_{max} = lfloor frac{x}{T} floor$

则区间右端点 $r = l + d_{max} = l + lfloor frac{x}{T} floor = lfloor frac{l * T + x}{T} floor = lfloor frac{l * T + n - l * T}{T} floor = lfloor frac{n}{T} floor = lfloor frac{n}{lfloor frac{n}{l} floor} floor $

代码：

for(int l = 1, r = 0; l <= n; l = r + 1){
    if ((n / l) != 0)
        r = min(n / (n / l), n);
    else
        r = n;
    //进行计算
}

View Code

例题

BZOJ 1257:[CQOI2007]余数之和

给定 $n, k$ 计算 $$ sum_{i = 1}^{n} k ; mod ; i$$

将式子进行变形可得 $$sum_{i = 1}^{n} k ; - ; lfloor frac{k}{i} floor ; * ; i$$