整除分块学习笔记

白简の博客 / 2023-08-13 / 原文

模板

给定一个正整数 \(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;
}