题目传送门

零、参考资料

总结与思考：数论分块

【数学】数论分块（整除分块）

一、数论分块的相关概念

“数论分块”这个名词，其实比较模糊，没有一个广泛认同的严格定义。这里讲一下我个人的理解：
令\(\displaystyle f(i)=\lfloor \frac{n}{i} \rfloor\)
\(f(i)\)的值，随着\(i\)的增加而单调不增，如果我把\(f(1),f(2),\dots,f(n)\)从左到右排开，会发现其值呈现出“块状”，每一个“块”就是连续的一段，每个“块”中\(f(i)\)的值都是相同的
举个例子，\(n = 5\)
\(f(1)=5,f(2)=2,f(3)=f(4)=f(5)=1\)，一字排开，得到\(5,2,1,1,1\)，相同的分到一个“块”中，直观一点，写成：\([5],[2],[1,1,1]\)

数论分块从直观上来讲就是这个现象

数论分块中，块的右端是个很重要的位置。比如例子\(n=5\)中，三个块右端的编号分别是\(1,2,5\)

二、关于\(\displaystyle \lfloor \frac{n}{i} \rfloor\)的值域大小:

• 当\(1 ≤ i ≤ ⌊ \sqrt{n} ⌋\)时，\(\displaystyle \lfloor \frac{n}{i} \rfloor\)的不同数值个数显然是不超过\(\lfloor \sqrt n \rfloor\)。

• 当\(\displaystyle \lfloor \sqrt n \rfloor < i \le n\)时，因为\(\displaystyle 1 \le \lfloor \frac{n}{i} \rfloor \le \sqrt n\)，所以不同数值个数还是不超过\(\lfloor \sqrt n \rfloor\)。

综合上述两种情况，\(\displaystyle \lfloor \frac{n}{i} \rfloor\)的不同数值个数严格不大于\(2 \sqrt n\)

三、结论一：假设某个块的\(f\)值为\(t\)，那么这个块右端的下标是$ \displaystyle \lfloor \frac{n}{t} \rfloor$

如果一个块的\(f\)值是\(t\)，对于其中的数\(x\)，应当满足\(\displaystyle \lfloor \frac{n}{x} \rfloor=t\)，即\(n = t x + r ( 0 ≤ r < x )\)，从这个式子中就可以看出\(x\)的取值是连续的一段整数。块的右端就是满足上式的最大\(x\)，也就是说\(x\times t ≤ n\)的最大\(x\)，那么显然\(\large \displaystyle x_{max}= \lfloor \frac{n}{t} \rfloor\)

四、结论2: \(f(i)\)的值域和块右端下标集合是相同的

比如上面那个例子，值域是\(\{1,2,5\}\)，块右端下标集合也是\(\{1,2,5\}\)

解释：

假设一个块的\(f\)值是\(t\)，右端是\(x\)，那么\(\displaystyle \lfloor \frac{n}{t} \rfloor=x, \lfloor \frac{n}{x} \rfloor=t\)

也就是说\(x\)和\(t\)一一对应，不同块的\(f\)值不会相同，一个\(f\)值也不会对应多个块，这就说明了块“右端“集合和\(f\)的值域值域这两个集合大小相同。

那么元素是否也是相同的呢？是的，因为假设一个元素\(p\)属于"块右端"集合，那么根据“块右端”的计算方法，得知某个肯定存在某个\(t\)使得\(\displaystyle \lfloor \frac{n}{t} \rfloor=p\)，也就是\(f(t)=p\)，也就是说\(p\)也属于\(f\)的值域集合。

因为两个集合大小相同，而且“块右端”集合中的每个元素也在值域集合中出现，所以这两个集合相等。

五、结论3: 当\(x \le \lfloor \sqrt n \rfloor\)时，\(f(x)\)的值严格单调增

六、本题解析

原式：$$\large \sum_{i=1}^{n} k \ % \ i$$

子项变形：

将子项变形代入原式：

显然，\(\large \displaystyle ⌊\frac{k}{i}⌋\) 是最棘手的，如果暴力枚举\(i\),数据范围是\(10^9\),肯定会\(TLE\),要想办法优化。

根据前面我们准备好的知识储备，我们知道这个答案由连续 \(2\sqrt{k}\) 段不同的取值组成，我们枚举下届，并利用公式计算出上界：每种取值下界 \(l\) 和 上界 \(r\), 通过

即可求得每一段对答案的贡献。 其中\(\displaystyle \sum_{i=l}^{r}i\)可以用等差数列求和公式计算:\(\displaystyle \sum_{i=l}^{r}i=\frac{(l+r)*(r-l+1)}{2}\)

七、算法设计

算法就很好设计了：

设 \(l=1\)，算出上界 \(r\)。计算这段的贡献

使 \(l=r+1\)，即跳到下一段计算贡献。

重复直到算完 \([1,n]\) 里所有段。

八、\(Tips\)

当 \(⌊k/l⌋=0\) 的时候，显然这段以及后面（有单调性）已经没有贡献了，可以 break。
注意右端点和 \(n\) 取个 \(min\)，因为 \(>n\) 没有贡献了。

九、实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//数论分块，余数之和，本题是很多其它题的基础，需要背诵
// j(n,k)=k%1+k%2+k%3+…+k%n
LL n, k, l, r;
LL ans;
int main() {
    // 1、当k/l=0的时候，显然这段以及后面（有单调性）已经没有贡献了，可以 break。
    // 2、注意右端点和n取个min，因为>n没有贡献了。
    cin >> n >> k;
    ans = n * k;
    for (l = 1; l <= n; l = r + 1) { //枚举左端点,每次跳着走，下次的位置就是本次r的位置+1
        if (k / l == 0) break;
        r = min(k / (k / l), n); //右边界
        //等差数列求和：左到右边界内，是公差为1的等差数列，
        ans -= (k / l) * (l + r) * (r - l + 1) / 2; //首项+末项 乘以 项数 除以2
    }
    printf("%lld\n", ans);
    return 0;
}