题解 | 余数求和

这题其实就是求 $\sum_{i=1}^{n}{k\space mod\space i}$
这题和整除分块又有什么关系呢？
mod没有什么特殊的性质，所以我们将它展开来，就变成了 $\sum_{i=1}^{n}{k\space-\lfloor \frac{k}{i} \rfloor*i}$
于是我们就看到了一个熟悉的形式，也就是整除分块的一般形式

再次改一下这个式子 $n*k-\sum_{i=1}^{n}{\lfloor \frac{k}{i}\rfloor*i}$
那么 $\sum_{i=1}^{n}{\lfloor \frac{k}{i}\rfloor*i}$ 和普通的整除分块有什么差别呢？

~~其实就是多了一个i~~

确实，就是多了一个i而已，只需要简单的化简一下，这个i就对我们的处理没有什么影响了

因为我们知道，对于一个整除分块 $\sum_{i=l}^{r}{\lfloor\frac{k}{i}\rfloor}$ ，其中的每个值都是相同的，于是我们可以设 $T=\lfloor\frac{k}{i}\rfloor$

式子就化为了 $\sum_{i=l}^{r}T*i \\ =\sum_{i=l}^{r}{T}*\sum_{i=l}^{r}i$
也就是说，其实这个式子前半段是一个整除分块，后半段是一个首项为l，公差为1的等差数列

至此，我们就圆满的解决了这个问题，可以在 $O(\sqrt{n})$ 的时间内解决本题

#include <bits/stdc++.h>

#define ll long long

ll n, k;
ll ans = 0;

int main() {
    scanf("%lld%lld", &n, &k);
    ans = n * k;
    for(int l = 1, r = 1; l <= n; l = r + 1) {
        if(k/l != 0) r = std::min(k / (k / l), n);
        else r = n;
        ans = ans - 1ll * ((r+l) * (k/l) * (r-l+1)) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}