【洛谷P2261】余数求和

题目大意:给定 n, k,求\(\sum\limits_{i=1}^n k\%n\) 的值。

题解:除法分块思想的应用。

\(x\%y=x-y\lfloor {x\over y}\rfloor\),因此只需快速求出 \(\sum\limits_{i=1}^n {k\over i}\) 即可。

引理:\(i\in [1,k], {k\over i}\) 最多只有不超过 \(2\sqrt k\) 个不同的值。(分情况讨论即可得出)

现在,只需找出每一段的起点和终点即可根据等差数列求和的方式来在 \(O(\sqrt(n))\) 的时间内求得答案。

引理:\(i\in [x,\lfloor k/{\lfloor k/x \rfloor}\rfloor]\) 时,\(k \over i\) 的值都相等。

代码如下

#include <bits/stdc++.h>
using namespace std; long long n,k,ans; int main(){
scanf("%lld%lld",&n,&k);
ans=n*k;
for(int l=1,r;l<=n;l=r+1){
r=k/l?min(k/(k/l),n):n;
ans-=(k/l)*(l+r)*(r-l+1)/2;
}
printf("%lld\n",ans);
return 0;
}
上一篇:iOS 离屏渲染的研究


下一篇:hibernate注解详解