数论分块

LXcjh4998 · 2025-04-14 21:06:09 · 算法·理论

本文原载于博客园。

前言

数论分块可以快速计算形如 \displaystyle S(n)=\sum_{i=1}^nf(i)g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right) 的式子。

若可以预处理 f(n) 的前缀和 \displaystyle s(n)=\sum_{i=1}^nf(i) 或 O(1) 计算 s(r)-s(l)，则数论分块可以在 O(\sqrt{n}) 的时间内计算 S(n)。

主要思想

注意到存在 i 不同，但 \left\lfloor\dfrac{n}{i}\right\rfloor 相同的情况。

因此，如果我们把 \left\lfloor\dfrac{n}{i}\right\rfloor 相同的数一同计算，就可以降低时间复杂度。

那么，对于一个正整数 l，我们如何找到最大的正整数 r，使得 \left\lfloor\dfrac{n}{l}\right\rfloor=\left\lfloor\dfrac{n}{r}\right\rfloor 呢？

先给出结论：r=\left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor。

以下是这一结论的证明：

设 l\le i 且 \left\lfloor\dfrac{n}{l}\right\rfloor=\left\lfloor\dfrac{n}{i}\right\rfloor。

则有 \left\lfloor\dfrac{n}{l}\right\rfloor=\left\lfloor\dfrac{n}{i}\right\rfloor\le\dfrac{n}{i}，即 \left\lfloor\dfrac{n}{l}\right\rfloor\le\dfrac{n}{i}。

所以 \left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor\ge\left\lfloor\dfrac{n}{\frac{n}{i}}\right\rfloor=\lfloor i\rfloor=i，即 i\le\left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor。

又因为 r 为最大的满足条件的正整数，所以 r=\left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor。

显然，数论分块的时间复杂度与 \left\lfloor\dfrac{n}{i}\right\rfloor 不同取值的数量相关。

我们有这一结论：\left\lfloor\dfrac{n}{i}\right\rfloor 最多有 2\left\lfloor\sqrt{n}\right\rfloor 种不同的取值。

证明：

• 当 1\le i\le\left\lfloor\sqrt{n}\right\rfloor 时，最多有 \left\lfloor\sqrt{n}\right\rfloor 种不同的取值。
• 当 \left\lfloor\sqrt{n}\right\rfloor<i\le n 时，有 \left\lfloor\dfrac{n}{i}\right\rfloor\le\left\lfloor\sqrt{n}\right\rfloor，最多有 \left\lfloor\sqrt{n}\right\rfloor 种不同的取值。

综上，\left\lfloor\dfrac{n}{i}\right\rfloor 最多有 2\left\lfloor\sqrt{n}\right\rfloor 种不同的取值。

因此，数论分块的时间复杂度是 O(\sqrt{n}) 的。

实现

以下为求 S(n) 的流程：

int S(int n){
    int ans=0;
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        ans+=(s(r)-s(l-1))*g(n/l);
    }
    return ans;
}

数论分块的拓展

高维数论分块

当和式变为含有 a_1,a_2,\cdots,a_k 时，右端点 r 的表达式由一维的 \left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor 变为 \displaystyle\min_{i=1}^k\left\{\left\lfloor\dfrac{a_i}{\lfloor\frac{a_i}{l}\rfloor}\right\rfloor\right\}。

显然，只有对于每个 a_i 的右端点都取最小值，才能保证对于每个 a_i，都有 \left\lfloor\dfrac{a_i}{l}\right\rfloor=\left\lfloor\dfrac{a_i}{r}\right\rfloor。

一般我们用的较多的是二维形式，此时可将代码中的 r=n/(n/l) 替换成 r=min(n/(n/l),m/(m/l))。

向上取整的数论分块

对于一个正整数 l，最大的满足 \left\lceil\dfrac{n}{l}\right\rceil=\left\lceil\dfrac{n}{r}\right\rceil 的正整数 r 为 \left\lfloor\dfrac{n-1}{\lfloor\frac{n-1}{l}\rfloor}\right\rfloor。

证明：

注意：当 l=n 时，上式会出现分母为 0 的错误，需要特殊处理。

其他奇形怪状的数论分块

以计算含有 \left\lfloor\sqrt{\dfrac{n}{i}}\right\rfloor 的和式为例。

考虑求出满足 \left\lfloor\sqrt{\dfrac{n}{l}}\right\rfloor=\left\lfloor\sqrt{\dfrac{n}{r}}\right\rfloor 的最大正整数 r。

设 l\le i，且满足 \left\lfloor\sqrt{\dfrac{n}{l}}\right\rfloor=\left\lfloor\sqrt{\dfrac{n}{i}}\right\rfloor。

则有 \left\lfloor\sqrt{\dfrac{n}{l}}\right\rfloor=\left\lfloor\sqrt{\dfrac{n}{i}}\right\rfloor\le\sqrt{\dfrac{n}{i}}，即 \left\lfloor\sqrt{\dfrac{n}{l}}\right\rfloor^2\le\dfrac{n}{i}。

所以 \Bigg\lfloor\dfrac{n}{{\lfloor\sqrt{n/l}\rfloor}^2}\Bigg\rfloor\ge\left\lfloor\dfrac{n}{\frac{n}{i}}\right\rfloor=\lfloor i\rfloor=i，即 i\le \Bigg\lfloor\dfrac{n}{{\lfloor\sqrt{n/l}\rfloor}^2}\Bigg\rfloor 。

又因为 r 为最大的满足条件的正整数，所以 r=\Bigg\lfloor\dfrac{n}{{\lfloor\sqrt{n/l}\rfloor}^2}\Bigg\rfloor。

再考虑 \left\lfloor\sqrt{\dfrac{n}{i}}\right\rfloor 最多有几种不同的取值。

• 当 i\le\left\lfloor\sqrt[3]{n}\right\rfloor 时，最多有 \left\lfloor\sqrt[3]{n}\right\rfloor 种不同的取值。
• 当 \left\lfloor\sqrt[3]{n}\right\rfloor<i\le n 时，有 \left\lfloor\sqrt{\dfrac{n}{i}}\right\rfloor\le\left\lfloor\sqrt[3]{n}\right\rfloor，最多有 \left\lfloor\sqrt[3]{n}\right\rfloor 种不同的取值。

综上，\left\lfloor\sqrt{\dfrac{n}{i}}\right\rfloor 最多有 2\left\lfloor\sqrt[3]{n}\right\rfloor 种的取值。 所以此时数论分块的时间复杂度为 O(\sqrt[3]{n})。

其他的情况大致也是这么推导的，依照上述步骤去分析即可。