正题

评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P2261

---

题目大意

求${\sum }_{i=1}^{n}k\%i$。

---

解题思路

将$k\%i$展开一下，$k-i\ast \lfloor k/i\rfloor$，然后答案就是
${\sum }_{i=1}^{n}k-i\ast \lfloor k/i\rfloor$
将k取出来
$nk-{\sum }_{i=1}^{n}i\ast \lfloor k/i\rfloor$
然后用等差公式分多块计算${\sum }_{i=1}^{n}i\ast \lfloor k/i\rfloor$

---

code

#include<cstdio> #include<algorithm> using namespace std; long long n,ans,k; int main() {scanf("%lld%lld",&n,&k);ans=n*k;for(int x=1,gx;x<=n;x=gx+1){gx=k/x?min(k/(k/x),n):n;ans-=(k/x)*(x+gx)*(gx-x+1)/2;}printf("%lld",ans); }

总结

以上是生活随笔为你收集整理的P2261-[CQOI2007]余数求和【数论,约数】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。