题解 | #余数求和#

题目链接

PEEK66 余数求和

题目描述

对于给定的正整数 $n$ 和 $k$ ( $1 \le n, k \le 10^9$ )，求表达式 $\sum_{i=1}^{n} (k \pmod i)$ 的值。

解题思路

本题要求计算 $\sum_{i=1}^{n} (k \pmod i)$ 。

首先，一个直接的想法是循环 $i$ 从 $1$ 到 $n$ ，累加每一个 $k \pmod i$ 的值。但由于 $n$ 的范围可以达到 $10^9$ ，这种 $O(n)$ 的朴素算法显然会超时。我们需要寻找更高效的方法。

我们可以利用取模运算和整除运算之间的关系来进行数学变换。我们知道，对于任意正整数 $k$ 和 $i$ ，有：

$k \pmod i = k - i \cdot \lfloor k/i \rfloor$

将这个关系代入原求和式中，得到：

$\sum_{i=1}^{n} (k \pmod i) = \sum_{i=1}^{n} (k - i \cdot \lfloor k/i \rfloor)$

我们可以将这个和式拆分为两部分：

$= \sum_{i=1}^{n} k - \sum_{i=1}^{n} i \cdot \lfloor k/i \rfloor$

$= n \cdot k - \sum_{i=1}^{n} i \cdot \lfloor k/i \rfloor$

现在，问题转化为了如何快速计算 $S(n, k) = \sum_{i=1}^{n} i \cdot \lfloor k/i \rfloor$ 。

这个和式的关键部分是 $\lfloor k/i \rfloor$ 。我们在此前的题目中已经知道， $\lfloor k/i \rfloor$ 的值在 $i$ 连续变化时，会在很多区间内保持不变。这提示我们可以使用整除分块技巧。

我们按 $\lfloor k/i \rfloor$ 的值进行分块。对于一个块，其起始位置为 $l$ ，块内所有的 $i$ 都有相同的 $\lfloor k/i \rfloor$ 值，我们记为 $v = \lfloor k/l \rfloor$ 。这个块的结束位置 $r$ 是满足 $\lfloor k/r \rfloor = v$ 的最大整数，可以计算得出 $r = \lfloor k/v \rfloor$ 。同时，由于我们的求和上限是 $n$ ，所以块的实际结束位置应该是 $\min(n, \lfloor k/v \rfloor)$ 。

对于从 $l$ 到 $r$ 的这一个块，它对 $S(n, k)$ 的贡献是：

$\sum_{i=l}^{r} i \cdot \lfloor k/i \rfloor = \sum_{i=l}^{r} i \cdot v = v \cdot \sum_{i=l}^{r} i$

其中 $\sum_{i=l}^{r} i$ 是一个等差数列求和，其值为 $\frac{(l+r)(r-l+1)}{2}$ 。

因此，我们可以通过迭代这些块来计算 $S(n, k)$ 。从 $l=1$ 开始，计算出当前块的 $v$ 和 $r$ ，累加该块的贡献，然后将下一个块的起始位置更新为 $l = r+1$ ，直到 $l > n$ 。

当 $i > k$ 时， $\lfloor k/i \rfloor = 0$ ，这些项对 $S(n, k)$ 的贡献为零。所以我们的分块循环实际上最多只会进行到 $l > \min(n, k)$ 。整个算法的时间复杂度大约是 $O(\sqrt{k})$ ，对于 $10^9$ 的数据规模是完全可以接受的。

代码

cpp
java
python

#include <iostream>
#include <algorithm>

using namespace std;

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

    long long sum_f = 0;
    for (long long l = 1, r; l <= n; l = r + 1) {
        long long v = k / l;
        if (v == 0) {
            // 当 k/l 等于0时，后续所有项的 i * floor(k/i) 也都为0，可以提前结束
            break;
        }
        r = min(n, k / v);
        // 等差数列求和: (首项 + 末项) * 项数 / 2
        long long sum_i = (l + r) * (r - l + 1) / 2;
        sum_f += v * sum_i;
    }

    long long ans = n * k - sum_f;
    cout << ans << endl;

    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 k = sc.nextLong();

        long sumF = 0;
        for (long l = 1, r = 0; l <= n; l = r + 1) {
            long v = k / l;
            if (v == 0) {
                // 当 k/l 等于0时，后续所有项的 i * floor(k/i) 也都为0，可以提前结束
                break;
            }
            r = Math.min(n, k / v);
            // 等差数列求和: (首项 + 末项) * 项数 / 2
            long sumI = (l + r) * (r - l + 1) / 2;
            sumF += v * sumI;
        }

        long ans = n * k - sumF;
        System.out.println(ans);
    }
}

import sys

def solve():
    n, k = map(int, input().split())

    sum_f = 0
    l = 1
    while l <= n:
        v = k // l
        if v == 0:
            # 当 k/l 等于0时，后续所有项的 i * floor(k/i) 也都为0，可以提前结束
            break
        r = min(n, k // v)
        # 等差数列求和: (首项 + 末项) * 项数 / 2
        sum_i = (l + r) * (r - l + 1) // 2
        sum_f += v * sum_i
        l = r + 1
    
    ans = n * k - sum_f
    print(ans)

solve()

算法及复杂度

算法：数论、整除分块
时间复杂度：核心计算是整除分块，其迭代次数取决于 $\lfloor k/i \rfloor$ 的不同取值个数，大约为 $2\sqrt{k}$ 。同时循环不超过 $n$ 。因此总时间复杂度为 $O(\sqrt{\min(n, k)})$ 。
空间复杂度： $O(1)$ ，没有使用额外的与输入规模相关的存储空间。