[CQOI2007] 余数求和

1 数学推导：将模运算转化为除法

题目要求计算：

直接计算模运算很难进行优化。我们需要利用模运算的定义公式：

核心: 这个公式的含义是: a对b的余数,就是a里面去除整块的b,成功的把余数问题转成整除问题

将这个公式代入原式：

利用求和符号的线性性质，我们可以把式子拆成两部分：

第一部分 $\sum_{i=1}^n k$ 很简单，就是 $n$ 个 $k$ 相加：

现在的核心任务变成了快速计算减号后面的部分：

2 整除分块的应用

观察式子 $\sum (i \times \lfloor \frac{k}{i} \rfloor)$，我们发现 $\lfloor \frac{k}{i} \rfloor$ 的值呈块状分布。 对于同一个块区间 $[l, r]$，$\lfloor \frac{k}{i} \rfloor$ 的值是一个常数，设为 val。

那么在区间 $[l, r]$ 内，这一段的贡献是：

这就变成了：(当前块的常数值) $\times$ (当前块下标 $i$ 的等差数列和)

等差数列求和公式大家都很熟悉：

3 代码深度解析

现在我们对照你的代码来看每一行在做什么。

变量定义与初始化

        
1
2
3
4

        // ans 用来存储后面那一坨 ∑(i * floor(k/i)) 的值
// 注意最后要用 n*k 减去它
ll ans = 0; 

    

循环结构 (整除分块核心)

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

        // 循环范围：只枚举到 min(n, k)
// 为什么？
// 1. 如果 i > n，题目不要求计算。
// 2. 如果 i > k，那么 floor(k/i) = 0，对减数部分没有贡献，不需要算。
for(int l=1,r; l <= min(k,n); l = r+1){
    
    // 1. 确定当前块的右端点 r
    // 公式 r = k / (k / l) 是整除分块的标准公式
    // 如果算出来的 r 超过了 n，我们要把它截断在 n，因为题目只要算到 n
    // 但是因为循环条件里已经写了 min(k,n)，这里的 r = min(r, n) 
    // 主要是为了防止 r 跳出 n 的边界（当 n < k 时）
    r = k/(k/l); 
    if (r > n) r = n; // 你的代码写的是 r = min(r, n)，效果一样
    
    // 2. 计算当前块的贡献
    // 贡献 = 值 * 区间下标和
    // 值 = (k/l)
    // 区间下标和 = (l+r)*(r-l+1)/2  <-- 等差数列求和
    ans += (ll)(k/l)*(l+r)*(r-l+1)/2;
}

    

最终计算

        
1
2
3
4

        // 套用最开始推导的公式： Ans = n*k - Sum
ans = (ll)n*k - ans;
printf("%lld\n",ans);

    

4 几个关键细节 QA

Q1: 为什么要用 min(n, k) 作为循环上限？

• 当 $n \le k$ 时：我们只需要算到 $n$，所以循环到 $n$ 结束。
• 当 $n > k$ 时：对于 $i > k$ 的部分，$\lfloor \frac{k}{i} \rfloor = 0$。也就是说，在减号后面的式子里，这部分全是 $0$，不需要减。所以我们只需要算出 $1$ 到 $k$ 的减数和即可。

Q2: 为什么你的代码里有 r = min(r, n) 这种逻辑？ 虽然循环条件限制了 l <= min(k,n)，但是计算出来的 r (即 k/(k/l)) 可能会直接跳过 $n$。 比如 $n=5, k=10$。 当 $l=1$ 时，$\lfloor 10/1 \rfloor = 10$，计算出的右端点 $r = 10/(10/1) = 10$。 但是题目只让你算到 $n=5$。如果不取 min，你就会把 $6,7,8,9,10$ 的贡献也算进去了，导致错误。所以必须强行把右端点限制在 $n$ 以内。 (注：你的代码里 r = min(r,n) 写得很对，但由于你循环条件里写了 min(k,n)，其实如果 $n > k$，r 不会超过 $n$；主要是防 $n < k$ 的情况)。

Q3: 数据范围与类型 题目中 $n, k \le 10^9$。

• 计算 n * k 会达到 $10^{18}$ 级别，必须用 long long。
• 等差数列求和 (l+r)*(r-l+1)/2 也会很大，必须强制转换 (ll) 计算。

5 复杂度分析

• 时间复杂度：我们知道整除分块的块数是 $O(\sqrt{k})$ 级别的。所以整个算法的时间复杂度是 $O(\sqrt{k})$。
  • 当 $k=10^9$ 时，$\sqrt{k} \approx 31622$，这在 1秒 的时限内绰绰有余。
• 空间复杂度：$O(1)$。

总结

你的代码逻辑非常清晰，是一个标准的整除分块模板。

1. 转化： 将模运算转化为除法减法。
2. 分块： 利用 $\lfloor \frac{k}{i} \rfloor$ 的性质加速计算。
3. 求和： 结合等差数列公式计算区间贡献。

这道题是后续学习 莫比乌斯反演 和 杜教筛 的基础，务必熟练掌握 l = r + 1 和 r = k / (k / l) 这一套写法。

代码

        
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
26
27
28

        /* author: Rainboy  email: rainboylvx@qq.com  time: 2020年 06月 30日 星期二 16:17:16 CST */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
typedef long long ll;

int n,m;
int k,c;

void init(){
    scanf("%d%d",&n,&k);
    ll ans = 0;
    for(int l=1,r;l<=min(k,n);l = r+1){
        r = k/(k/l);
        r = min(r,n);
        ans += (ll)(k/l)*(l+r)*(r-l+1)/2;
    }
    ans = (ll)n*k - ans;
    printf("%lld\n",ans);
}

int main(){
    init();
    return 0;
}