洛谷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;
}