2013-11-15 21:55

原題傳送門http://www.lydsy.com/JudgeOnline/problem.php?id=1257

要求求sigma k mod i(i<=n)

那么我們可以轉化為sigma k-(k div i)*i;

對于k div i,我們可以發現，對于k，i在遞增時，k div i的值是遞減且存在連續區間的，那么我們可以每次二分每個區間的首位，然后對于i用等差數列求和公式算就可以了（相當于把相等的k div i提出來），然后更新答案就好了

//By BLADEVIL varn, k :int64;i, j :longint;ans :int64;mid, r, l :int64;now, pi :int64;beginread(n,k);j:=n;ans:=n*k;while j>0 dobeginnow:=k div j;l:=1; r:=j;while l<=r dobeginmid:=(l+r) div 2;if k div mid=now thenbeginpi:=mid;r:=mid-1;end else l:=mid+1;end;ans:=ans-now*(pi+j)*(j-pi+1) div 2;j:=pi-1;end;writeln(ans); end.

?

轉載于:https://www.cnblogs.com/BLADEVIL/p/3433528.html

總結

以上是生活随笔為你收集整理的bzoj1257 数学整理二分查询的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。