整除分块学习笔记

· · 个人记录

模板

给定一个正整数 n，其中 n \leq 10^9，考虑求

\sum_{i=1}^n \left\lfloor \dfrac{n}{i}\right\rfloor

我们可以直接模拟，时间复杂度 \operatorname{O}(n)。

但这样显然无法通过这个问题。

思想

我们把 n=10 的情况列出来：

\boxed{\left\lfloor\dfrac{10}{1}\right\rfloor=10}, \boxed{\left\lfloor\dfrac{10}{2}\right\rfloor=5}, \boxed{\left\lfloor\dfrac{10}{3}\right\rfloor=3}, \boxed{\left\lfloor\dfrac{10}{4}\right\rfloor=2}, \boxed{\left\lfloor\dfrac{10}{5}\right\rfloor=2}, \boxed{\left\lfloor\dfrac{10}{6}\right\rfloor=1}, \boxed{\left\lfloor\dfrac{10}{7}\right\rfloor=1}, \boxed{\left\lfloor\dfrac{10}{8}\right\rfloor=1}, \boxed{\left\lfloor\dfrac{10}{9}\right\rfloor=1}, \boxed{\left\lfloor\dfrac{10}{10}\right\rfloor=1}

容易发现，对于一些不同的 i，有相同的 \left\lfloor \dfrac{n}{i} \right\rfloor，我们可不可以把这些相同的部分一并计算来降低时间复杂度呢？

显然是可以的。

我们把这些有相同 \left\lfloor \dfrac{n}{i} \right\rfloor 值的区间称为一个块，那么问题在于我们如何找到块长，或者说块的左右端点。

假设我们已知某个块的左端点 l，求解块的右端点 r。

记有整数 k=\left\lfloor \dfrac{n}{i} \right\rfloor(i \in \left[l,r \right])，表示这个块的数值。

显然有

k=\left\lfloor \dfrac{n}{i} \right\rfloor=\left\lfloor \dfrac{n}{l} \right\rfloor

即 i \times k \leq n，那么我们可以发现，当 i=r 时，r \times k 的值最大且 r \times k \leq n。

那么有：

r=\left\lfloor \dfrac{n}{k} \right\rfloor

又因为有：

k=\left\lfloor \dfrac{n}{l} \right\rfloor

代入得：

r=\left\lfloor \dfrac{n}{\left\lfloor \dfrac{n}{l} \right\rfloor} \right\rfloor

Code

long long H(int n) {
    long long res = 0;
    if(n == 0)
        return 0;
    int l = 1,r;
    while(l <= n) {
        r = n / (n / l);
        res += 1ll * (r - l + 1) * (n / l);
        l = r + 1;
    }
    return res;
}

性质

证明：对于 i \leq \sqrt{n}，最多有 \sqrt{n} 种取值；而对于 i > \sqrt{n}，有 \dfrac{n}{i} < \sqrt{n}，所以也最多只有 \sqrt{n} 种取值，所以最多也只有 2\sqrt{n} 种取值。

练习

UVA11526 H(n)（模板题）

[CQOI2007] 余数求和

\text{END}