题目分析

题意简述

给定两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^9$），计算 $\sum_{i=1}^{n} (k \bmod i)$，即 $k$ 对 $1$ 到 $n$ 每个数取模后的总和。

输入

• 输入包含多组测试用例，每组给出 $n$ 和 $k$。

输出

• 对于每组测试用例，输出所求的和。

解题思路

直接计算的问题

直接遍历 $i$ 从 $1$ 到 $n$ 计算 $k \bmod i$ 并累加，时间复杂度为 $O(n)$。当 $n$ 和 $k$ 很大时（如 $10^9$），这种暴力方法会超时。

数学优化

观察到：

1. 当 $i > k$ 时，$k \bmod i = k$，因此这部分的和可以直接计算为 $(n - k) \times k$（如果 $n > k$）。
2. 当 $i \leq k$ 时，$k \bmod i = k - i \times \lfloor \frac{k}{i} \rfloor$。可以利用数论分块优化计算：
   • 对于固定的 $q = \lfloor \frac{k}{i} \rfloor$，$i$ 的取值范围是 $\left[ \lfloor \frac{k}{q+1} \rfloor + 1, \lfloor \frac{k}{q} \rfloor \right]$。
   • 通过分块计算，将时间复杂度从 $O(n)$ 降低到 $O(\sqrt{k})$。

算法步骤

1. 处理 $i > k$ 的情况：直接计算 $(n - k) \times k$。
2. 处理 $i \leq k$ 的情况：
   • 使用数论分块，枚举 $q = \lfloor \frac{k}{i} \rfloor$ 的所有可能值。
   • 对于每个 $q$，计算对应的 $i$ 的范围，并累加 $k \bmod i$ 的总和。

代码实现

#include <cstdio>
#include <cstdlib>  // 添加exit函数

using namespace std;

int main() {
    long long k, n;
    while (scanf("%lld%lld", &n, &k) == 2) {
        if (k == 0) {  // 处理k=0的特殊情况
            printf("0\n");
            continue;
        }
        
        long long ans = 0;
        
        // 处理i > k的情况
        if (n > k) {
            ans += (n - k) * k;
            n = k;
        }
        
        // 处理i <= k的情况
        long long p = 1;
        for (int i = 1; ; i++) {
            if (k / i <= k / (i + 1) + 2) {
                p = i;
                break;
            }
        }
        
        if (n <= k / (p + 1)) {
            for (int i = 1; i <= n; i++) {
                ans += k % i;
            }
            printf("%lld\n", ans);
            continue;
        }
        
        for (int i = p; i >= 1; i--) {
            long long cnt = k / i - k / (i + 1);
            long long t = k % (k / i) + (cnt - 1) * i;
            if (n < k / (i + 1) + 1) break;
            if (n < k / i) cnt = n - k / (i + 1);
            ans += cnt * (2 * t + (1 - cnt) * i) / 2;
        }
        
        for (int i = 1; i <= k / (1 + p); i++) {
            ans += k % i;
        }
        
        printf("%lld\n", ans);
    }
    return 0;
}

代码说明

1. 输入处理
   • 使用 scanf 读取多组测试用例的 $n$ 和 $k$。
2. 直接计算 $i > k$ 的部分
   • 如果 $n > k$，直接计算 $(n - k) \times k$ 并累加到答案中。
3. 数论分块优化
   • 通过枚举 $q = \lfloor \frac{k}{i} \rfloor$ 的值，分块计算 $k \bmod i$ 的总和。
   • 使用等差数列求和公式加速计算。
4. 边界处理
   • 对于较小的 $i$，直接暴力计算；对于较大的 $i$，利用分块结果。

复杂度分析

• 时间复杂度：$O(\sqrt{k})$，主要来自数论分块的枚举。
• 空间复杂度：$O(1)$，仅使用常数空间。

示例

输入样例 1

5 3

输出样例 1

7

解释

$3 \bmod 1 + 3 \bmod 2 + 3 \bmod 3 + 3 \bmod 4 + 3 \bmod 5 = 0 + 1 + 0 + 3 + 3 = 7$。