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} \rfloor\)

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

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

根据除法分块（别在意它只是一个名字），这些值不重复的个数大约是\(\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\n",ans);

    return 0;

}

---

2018.7.23