数论分块

数论分块可以快速计算一些含有除法向下取整的和式 (即形如 \(\sum_{i=1}^{n} f(i) g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\) 的和式)。当可 以在 \(O(1)\) 内计算 \(f(r)-f(l)\) 或已经预处理出 \(f\) 的前缀和时，数论分块就可以在 \(O(\sqrt{n})\) 的时间内 计算上述和式的值。
它主要利用了富比尼定理 (\(Fubini's theorem\))，将 \(\big\lfloor\dfrac{n}{i}\big\rfloor\) 相同的数打包同时计算。

引入

洛谷 P1403 约数研究

题目转换一下就是求 \(f(n)=\sum_{i=1}^{n}\big\lfloor\dfrac{n}{i}\big\rfloor\)

朴素做法，遍历 \(1\sim n\) 求和，时间复杂度 \(O(n)\)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += n / i;
        }
        System.out.println(ans);
    }
}

不能解决 \(10^9\) 以上的数据范围，考虑优化

当 \(n=21\) 时，\(\big\lfloor\dfrac{n}{i}\big\rfloor\) 的值如下：

观察发现，\(\big\lfloor\dfrac{n}{i}\big\rfloor\) 的取值在连续的一段区间内是相同的，是”一块一块“的

如果我们知道了每一块的值和长度（左右边界），也就可以使用乘法运算来代替加法运算了

求某一值所在块的右端点

假设求 \(i\) 所在块的右端点

\(i\) 所在块的值为 \(k=\big\lfloor\dfrac{n}{i}\big\rfloor\)，则 \(k\leqslant\dfrac{n}{i}\)，所以 \(\big\lfloor\dfrac{n}{k}\big\rfloor\geqslant\left\lfloor\dfrac{n}{\frac{n}{i}}\right\rfloor=\big\lfloor i\big\rfloor=i\)

因此，\(i_{\max }=\left\lfloor\dfrac{n}{k}\right\rfloor=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor\)，即右端点为 \(\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor\)

实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long ans = 0;
        for (long l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            ans += n / l * (r - l + 1);
        }
        System.out.println(ans);
    }
}

时间复杂度分析

\(\text{ 分块的块数 }\leq 2\left\lfloor\sqrt{n}\right\rfloor\)

证明：

当 \(i \leq\lfloor\sqrt{n}\rfloor\) 时, \(\left\lfloor\dfrac{n}{i}\right\rfloor\) 有 \(\lfloor\sqrt{n}\rfloor\) 种取值。
当 \(i>\lfloor\sqrt{n}\rfloor\) 时, \(\left\lfloor\dfrac{n}{i}\right\rfloor \leq\lfloor\sqrt{n}\rfloor,\left\lfloor\dfrac{n}{i}\right\rfloor\) 至多有 \(\lfloor\sqrt{n}\rfloor\) 种取值。

综上，分块的块数\(\leq 2\left\lfloor\sqrt{n}\right\rfloor\)

因此，时间复杂度为 \(O(2\sqrt n)=O(\sqrt n)\)

例题

参考资料

【数论】整除分块（数论分块）_辞树c的博客-CSDN博客

549 整除分块（数论分块）- 董晓算法 - 哔哩哔哩

数论分块 - OI Wiki