题解 P2261 【[CQOI2007]余数求和】

zzlzk

2017-10-15 15:00:47

Solution

- 根据题目可以写出$ans=\sum\limits_{i=1}^{n}k\%i$ - 首先知道一点 $a\%b$ 可以表示为 $a-b*\lfloor\frac{a}{b}\rfloor$,写过高精取模的人应该都知道 - 所以 $ans=\sum\limits_{i=1}^{n}k-i*\lfloor\frac{k}{i}\rfloor=n*k-\sum\limits_{i=1}^{n}i*\lfloor\frac{k}{i}\rfloor$ - 然后 $\lfloor\frac{k}{i}\rfloor$ 可以出发分块来做,$\lfloor\frac{k}{i}\rfloor$大约有$\sqrt k$种取值,所以时间复杂度$O(\sqrt k)$ ```cpp #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int main() { ll n,k; scanf("%lld%lld",&n,&k); ll ans=n*k; for(ll l=1,r;l<=n;l=r+1) { if(k/l!=0) r=min(k/(k/l),n); else r=n; ans-=(k/l)*(r-l+1)*(l+r)/2; } printf("%lld",ans); return 0; } ``` 无耻的挂一个[blog](http://blog.csdn.net/nuclearsubmarines/article/details/78165951)