题解 | 余数求和 #

$[模板+数论分块]$

$\sum_{i=1}^{n}{(k \mod i)} = \sum_{i = 1}^{n}{(k - i\times\lfloor \frac{k}{i} \rfloor}) = \sum_{i=1}^{n}{k} -\sum_{i=1}^{n}{(k - i\times\lfloor \frac{k}{i} \rfloor}) = n\times k - \sum_{i=1}^{n}{i\times \lfloor \frac{k}{i} \rfloor}$

$\sum_{i=1}^{n}{ i\times\lfloor \frac{k}{i} \rfloor}$ ，是从 $1$ 到 $n$ ，但是是 $\lfloor \frac{k}{i} \rfloor$ ，如果 $n = k$ ，那就是数论分块模板；如果 $n < k$ ，将 $n$ 直接修改为 $k$ 没有问题；如果 $n > k$ ，那么对于 $k<i\leq n$ 的这部分 $i$ 来说， $\lfloor \frac{k}{i} \rfloor$ 的值为0，不用考虑，那么其实 $i$ 的范围为 $min(k,n)$

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;

    int n, k; cin >> n >> k;
    int sum = n * k;
    for(int i = 1; i <= min(k, n); i ++){
        int l = i, r = (k / (k / i));
        int len = r - l + 1;
        sum -= (i + i + len - 1) * len / 2 * (k / i);
        i = r;
    }
    cout << sum << endl;
    return 0;
}

但是上面的代码是错的

原因在于 $for$ 循环中的 $i$ 是做边界，当然 $i\leq min(k,n)$ 没有问题，但是忘记了考虑右边界的情况，得加上 $r = min(\{r, k,n\})$ 才正确

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n, k; cin >> n >> k;
    int ans = n * k;
    for(int i = 1; i <= min(n, k); i ++){
        int l = i, r = k / (k / i);
        r = min({r, k, n});
        int len = r - l + 1;
        ans -= (i + i + len - 1) * len / 2 * (k / i);
        i = r;
    }
    cout << ans << endl;
    return 0;
}