题解 | 余数求和

这题其实就是求
这题和整除分块又有什么关系呢？
mod没有什么特殊的性质，所以我们将它展开来，就变成了
于是我们就看到了一个熟悉的形式，也就是整除分块的一般形式

再次改一下这个式子
那么和普通的整除分块有什么差别呢？

其实就是多了一个i

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

因为我们知道，对于一个整除分块，其中的每个值都是相同的，于是我们可以设

式子就化为了
也就是说，其实这个式子前半段是一个整除分块，后半段是一个首项为l，公差为1的等差数列

至此，我们就圆满的解决了这个问题，可以在的时间内解决本题

#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;
}