数论分块也称整除分块,是一个竞赛中的常用小技巧

来看一个题目:

已知 f(n) = \sum_{i = 1}^{n} \left \lfloor \frac{n}{i} \right \rfloor,给定一个 n,求 f(n) 的值。

如果 1 \leq n \leq 10^6,直接枚举,时间 5ms

但是如果 1 \leq n \leq 10 ^ {12} 呢?

现在来介绍数论分块


给出如下表格,枚举 \left \lfloor \frac{n}{i} \right \rfloor:

$i$ 1 2 3 4 5 6 7 8 9 10
$\left \lfloor \frac{n}{i} \right \rfloor$ 10 5 3 2 2 1 1 1 1 1

观察到这个值是逐步变小的,且很多值都相等,这是整除操作的规律。

为了对这些整除的结果进行快速求和,自然能想到把它们分块,其中每块的 \left \lfloor \frac{n}{i} \right \rfloor 相同,将这一块一块一起算,就快多了。

那么问题来到,这个 \left \lfloor \frac{n}{i} \right \rfloor 一共有多少种取值?一共能把他分成多少块?

1)答:分块数小于 2 \sqrt{n} 种。

证明: i \leq \sqrt{n} 时, \frac{n}{i} 的值有 \Big\lbrace {\frac{n}{1},\frac{n}{2},\frac{n}{3},…,\frac{n}{\sqrt{n}}}\Big\rbrace,共 \sqrt{n}个,同理, i \gt \sqrt n时情况一样。所以总个数不超过 2 \sqrt n 个,复杂度为 \mathcal{O}(\sqrt{n})

2)证明:转自大佬

站内渲染不了,插件还是差点意思(或许版本问题)

Template

ll division_block(ll n){
    ll res = 0;
    for(ll l = 1, r; l <= n; l = r + 1){
        r = n / (n / l);
        res += n / l * (r - l + 1);
    }
    return res;
}

例题

P1403

P2261

P2424

CF1485C