题解 | #【模板】整除分块#

题目链接

题目描述

对于给定的正整数 $N$ ，求表达式 $\sum_{i=1}^{N} \lfloor \frac{N}{i} \rfloor$ 的值。

解题思路

本题是 整除分块（也称 数论分块）算法的模板题。

由于 $N$ 的范围可以达到 $10^{12}$ ，使用 $O(N)$ 的朴素循环来计算每一项的和是不可行的，会导致超时。我们需要一个更高效的算法。

核心观察

我们注意到，在表达式 $\lfloor \frac{N}{i} \rfloor$ 中，随着 $i$ 的增加，商的值并不是连续变化的，而是呈阶梯状下降。这意味着有许多连续的 $i$ 会得到完全相同的 $\lfloor \frac{N}{i} \rfloor$ 值。

例如，当 $N=10$ 时：

$i=1, \lfloor \frac{10}{1} \rfloor = 10$
$i=2, \lfloor \frac{10}{2} \rfloor = 5$
$i=3, \lfloor \frac{10}{3} \rfloor = 3$
$i=4,5, \lfloor \frac{10}{i} \rfloor = 2$
$i=6,7,8,9,10, \lfloor \frac{10}{i} \rfloor = 1$

我们可以把具有相同商值的连续区间 $i$ 看作一个“块”，对每个块进行整体计算，从而大大减少计算量。

块的边界

算法的关键在于，对于一个块的左边界 $l$ ，如何快速找到它的右边界 $r$ 。

假设当前块内所有 $i$ 的商都等于 $v = \lfloor \frac{N}{l} \rfloor$ 。我们想找到最大的 $r$ 使得 $\lfloor \frac{N}{r} \rfloor = v$ 。

这个右边界可以通过一个简单的公式得出： $r = \lfloor \frac{N}{v} \rfloor = \lfloor \frac{N}{\lfloor \frac{N}{l} \rfloor} \rfloor$ 。

算法流程

初始化答案 ans = 0，左边界 l = 1。
当 l <= N 时，循环执行：

a. 计算当前块的商 v = N / l。

b. 计算当前块的右边界 r = N / v。

c. 这个块包含的项数为 (r - l + 1)，每一项的值都是 v。将贡献 (r - l + 1) * v 累加到 ans 中。

d. 将左边界 l 更新为 r + 1，跳到下一个块的起始位置。
循环结束后，ans 即为所求答案。

可以证明， $\lfloor \frac{N}{i} \rfloor$ 的不同取值最多只有 $2\sqrt{N}$ 个，因此该算法的时间复杂度为 $O(\sqrt{N})$ ，足以通过本题。

代码

c++
java
python

#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;

    long long ans = 0;
    for (long long l = 1, r; l <= n; l = r + 1) {
        long long v = n / l;
        r = n / v;
        ans += (r - l + 1) * v;
    }

    cout << ans << "\n";

    return 0;
}

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) {
            long v = n / l;
            r = n / v;
            ans += (r - l + 1) * v;
        }

        System.out.println(ans);
    }
}

def solve():
    n = int(input())
    
    ans = 0
    l = 1
    while l <= n:
        v = n // l
        r = n // v
        ans += (r - l + 1) * v
        l = r + 1
        
    print(ans)

solve()

算法及复杂度

算法：整除分块 (Integer Division Block)
时间复杂度： $O(\sqrt{N})$ 。
空间复杂度： $O(1)$ 。