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

P2261 [CQOI2007]余数求和

题意：

求(G(n,k)=sum_{i=1}^n k mod i)

数据范围：

(1 le n,k le 10^9)

---

(G(n,k))
(=sum_{i=1}^n k-i*lfloor frac{k}{i} floor)
(=n*k-sum_{i=1}^n i*lfloor frac{k}{i} floor)

显然，(lfloor frac{k}{i} floor)的分布可能会有重复。

根据除法分块（别在意它只是一个名字），这些值不重复的个数大约是(sqrt k)

我们只需要统计每一块的值即可，注意到值在区间上的出现是单调递增的。

如果我们得到某一块最开始的下标(l)（可以从上一块的(r)得到），如何推得这一块的(r)呢？

其实很简单,(frac{k}{l})的余数是最大的，而(frac{k}{r})的余数显然得为0

设(t=frac{k}{l}),则(r=frac{k}{t})

加上不能越界的判断，完整的即为
(if t==0)
(r=n)
(else)
(r=min(n,frac{k}{t}))

对每一块直接统计即可

---

Code:

#include <cstdio>
#define ll long long
ll min(ll x,ll y){return x<y?x:y;}
ll k,ans,n,l,r,t;
int main()
{
    scanf("%lld%lld",&n,&k);
    ans=n*k;
    l=1;
    while(r!=n)
    {
        ll t=k/l;
        if(!t) r=n;
        else r=min(n,k/t);
        ans-=(r+1-l)*(l+r)*t/2;
        l=r+1;
    }
    printf("%lld
",ans);
    return 0;
}

---

2018.7.23