洛谷2261 [CQOI2007]余数求和

题意

求

$$\sum_{i=1}^n k \ \mathrm{mod} \ i$$

$n,k\le 10^9$

题解

经典的数值分块问题。

原式可以化为：

$$n\times k - \sum_{i=1}^n i\times \lfloor \dfrac{k}{i} \rfloor$$

问题就转化为求 $\sum_{i=1}^n i\times \lfloor \dfrac{k}{i} \rfloor$

可以发现 $\lfloor \dfrac{k}{i} \rfloor$ 相同的 $i$ 是连续的，所以可以按 $\lfloor \dfrac{k}{i} \rfloor$ 分块。

枚举当前块左端点 $l$ ，可以算出右端点 $r$ 。当前块的权值即为 $\lfloor \dfrac{k}{i} \rfloor \times (r-l+1)\times \dfrac{l+r}{2}$ （权值 $\times $ 区间长度 $\times$ 区间内 $i$ 的平均值）

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll n,k;

signed main()
{
    n=read(); k=read();
    ll ans=n*k;
    for (ll l=1,r,t;l<=n;l=r+1)
    {
        if ((t=k/l)!=0) r=min(k/t,n);
        else r=n;
        ans-=t*(r-l+1)*(l+r)/2;
    }
    return !printf("%lld",ans);
}