笔记 – 数论分块

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

来看一个题目：

已知 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:

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

为了对这些整除的结果进行快速求和，自然能想到把它们分块，其中每块的 \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