BISHI41 【模板】整除分块

在这里插入图片描述

求解思路

当 $n=5$ 时：

$i=1 \rightarrow \lfloor 5/1 \rfloor = 5$
$i=2 \rightarrow \lfloor 5/2 \rfloor = 2$
$i=3 \rightarrow \lfloor 5/3 \rfloor = 1$
$i=4 \rightarrow \lfloor 5/4 \rfloor = 1$
$i=5 \rightarrow \lfloor 5/5 \rfloor = 1$

可以看到：$i=3,4,5$ 对应的 $\lfloor 5/i \rfloor$ 都是 1，这一段可以批量计算。

对于当前的 $i$，设 $v = \lfloor \frac{n}{i} \rfloor$，则最大的 $j$ 满足 $\lfloor \frac{n}{j} \rfloor = v$ 是： $j = \left\lfloor \frac{n}{v} \right\rfloor$。

因此，我们可以按“值相同的区间”分块，每个区间的贡献是 $v \times (j - i + 1)$，然后直接跳到 $j+1$ 继续计算。

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer in = new StringTokenizer(br.readLine());

        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        long n = Long.parseLong(in.nextToken());

        long res = 0;

        long i = 1;

        while (i <= n) {
            long v = n / i; // 当前块的取值
            long j = n / v; // 当前块的右边界
            res += v * (j - i + 1); // 计算当前块的贡献
            i = j + 1; // 跳到下一个块的起点
        }

        out.println(res);
        out.flush();
        out.close();
        br.close();
    }