AcWing 199. 余数之和

题目传送门

零、参考资料

总结与思考：数论分块

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

一、数论分块的相关概念

“数论分块”这个名词，其实比较模糊，没有一个广泛认同的严格定义。这里讲一下我个人的理解：
令/(/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 k /% i=k – /left /lfloor /frac{k}{i} /right /rfloor /times i
/]

将子项变形代入原式：

/[/large /sum_{i=1}^{n} k / /% / i= n/times k – /sum_{i=1}^{n} /left /lfloor /frac{k}{i} /right /rfloor /times i
/]

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

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

/[/large /sum_{i=l}^{r} /left /lfloor /frac{k}{i} /right /rfloor * i =/sum_{i=l}^{r} /left /lfloor /frac{k}{l} /right /rfloor * i = /left /lfloor /frac{k}{l} /right /rfloor * /sum_{i=l}^{r}i
/]

即可求得每一段对答案的贡献。 其中/(/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;
}