洛谷P2261 [CQOI2007]余数求和 题解

题目链接：P2261 [CQOI2007]余数求和

题意：

给定 \(n,k\) ，求 \[ G(n,k)= \sum_{i=1}^{n}k \bmod i \] 数据范围：

\(1 \le n,k \le 10^9\) 。

考虑数论分块

注意到 \[ \begin{aligned} \sum_{i=1}^{n}k \bmod i &= \sum_{i=1}^{n}\left(k-i\left\lfloor\dfrac{k}{i}\right\rfloor\right)\\ &=nk-\sum_{i=1}^{n}i\left\lfloor\dfrac{k}{i}\right\rfloor \end{aligned} \] 若 \(k < n\) ，显然 \(\forall i > k\) 有 \(\left\lfloor\dfrac{k}{i}\right\rfloor=0\)

故可直接计算 \[ nk-\sum_{i=1}^{k}i\left\lfloor\dfrac{k}{i}\right\rfloor \] 若 \(k \ge n\) ，则判断一下右边界不要超过 \(n\) 即可

时间复杂度 \(\mathcal{O}(\sqrt{n})\)

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;int res=n*k;
    for(int l=1,r; l<=min(k,n); l=r+1)
    {
        r=min(k/(k/l),n);
        res-=(k/l)*(r-l+1)*(l+r)/2;
    }
    cout << res << endl;
    return 0;
}