题解 | #区间因数个数之和#

题目链接

题目描述

给定两个正整数 $L$ 和 $R$ ( $1 \le L \le R \le 10^{12}$ )，求值在 $[L, R]$ 区间内的所有整数的因数个数之和。形式化地，就是计算 $\sum_{i=L}^{R} d(i)$ 的值，其中 $d(i)$ 表示正整数 $i$ 的因数个数。

解题思路

本题要求计算区间 $[L, R]$ 内所有数的因数个数之和。直接对区间内每个数进行因数分解并计数，效率会很低。一个常见的优化思路是利用前缀和思想，将问题转化为计算两个从 $1$ 开始的区间的差：

$\sum_{i=L}^{R} d(i) = \left(\sum_{i=1}^{R} d(i)\right) - \left(\sum_{i=1}^{L-1} d(i)\right)$

这样，问题就变成了如何快速计算函数 $S(n) = \sum_{i=1}^{n} d(i)$ 。

让我们换一个角度来思考 $S(n)$ 的计算。与其枚举每个数 $i$ 并计算它的因数个数 $d(i)$ ，我们可以反过来考虑每个数 $j$ (从 $1$ 到 $n$ ) 作为因数，对总和贡献了多少次。

一个数 $j$ 是 $j, 2j, 3j, \dots, k \cdot j$ 的因数，其中 $k \cdot j \le n$ 。在 $1$ 到 $n$ 的范围内， $j$ 的倍数一共有 $\lfloor n/j \rfloor$ 个。这意味着，数字 $j$ 会作为因数出现 $\lfloor n/j \rfloor$ 次，每次都为因数总和贡献 $1$ 。

因此，我们可以得到一个新的求和公式：

$S(n) = \sum_{i=1}^{n} d(i) = \sum_{j=1}^{n} \lfloor n/j \rfloor$

现在问题变成了如何快速计算 $\sum_{j=1}^{n} \lfloor n/j \rfloor$ 。直接遍历 $j$ 从 $1$ 到 $n$ 的时间复杂度是 $O(n)$ ，对于很大的 $n$ 依然会超时。

这里就可以引入整除分块（也叫数论分块）技巧了。我们观察到，在 $j$ 的连续变化过程中， $\lfloor n/j \rfloor$ 的值会保持不变，形成一个个“块”。例如，当 $n=10$ 时：

$j=1$ , $\lfloor 10/1 \rfloor = 10$
$j=2$ , $\lfloor 10/2 \rfloor = 5$
$j=3$ , $\lfloor 10/3 \rfloor = 3$
$j=4, 5$ , $\lfloor 10/j \rfloor = 2$
$j=6, 7, 8, 9, 10$ , $\lfloor 10/j \rfloor = 1$

对于任意一个块的起始位置 $l$ ，该块内所有 $j$ 对应的 $\lfloor n/j \rfloor$ 的值都等于 $v = \lfloor n/l \rfloor$ 。这个块的结束位置 $r$ 是满足 $\lfloor n/r \rfloor = v$ 的最大整数，可以被证明为 $r = \lfloor n / \lfloor n/l \rfloor \rfloor = \lfloor n/v \rfloor$ 。

于是，我们可以按块进行迭代。对于每个从 $l$ 到 $r$ 的块，它包含的项数是 $(r - l + 1)$ ，每项的值都是 $\lfloor n/l \rfloor$ 。该块对总和的贡献就是 $(r - l + 1) \cdot \lfloor n/l \rfloor$ 。计算完一个块后，下一个块的起始位置就是 $r+1$ 。

这种分块方法的迭代次数大约是 $2\sqrt{n}$ 级别，所以计算 $S(n)$ 的时间复杂度可以优化到 $O(\sqrt{n})$ ，足以通过本题。

最终，我们分别计算 $S(R)$ 和 $S(L-1)$ ，相减即可得到答案。

代码

cpp
java
python

#include <iostream>

using namespace std;

// 使用整除分块计算 S(n) = sum_{i=1 to n} floor(n/i)
long long calculate(long long n) {
    if (n == 0) {
        return 0;
    }
    long long ans = 0;
    for (long long l = 1, r; l <= n; l = r + 1) {
        long long val = n / l;
        r = n / val;
        ans += (long long)(r - l + 1) * val;
    }
    return ans;
}

int main() {
    long long l, r;
    cin >> l >> r;
    cout << calculate(r) - calculate(l - 1) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    // 使用整除分块计算 S(n) = sum_{i=1 to n} floor(n/i)
    private static long calculate(long n) {
        if (n == 0) {
            return 0;
        }
        long ans = 0;
        for (long l = 1, r; l <= n; l = r + 1) {
            long val = n / l;
            r = n / val;
            ans += (long) (r - l + 1) * val;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long l = sc.nextLong();
        long r = sc.nextLong();
        System.out.println(calculate(r) - calculate(l - 1));
    }
}

import sys

# 使用整除分块计算 S(n) = sum_{i=1 to n} floor(n/i)
def calculate(n):
    if n == 0:
        return 0
    ans = 0
    l = 1
    while l <= n:
        val = n // l
        r = n // val
        ans += (r - l + 1) * val
        l = r + 1
    return ans

def solve():
    l, r = map(int, input().split())
    result = calculate(r) - calculate(l - 1)
    print(result)

solve()

算法及复杂度

算法：数论、整除分块
时间复杂度：我们使用整除分块计算两次前缀和，单次计算的复杂度为 $O(\sqrt{N})$ 。因此，总时间复杂度为 $O(\sqrt{R})$ 。
空间复杂度： $O(1)$ ，没有使用额外的与输入规模相关的存储空间。