脚本宝典收集整理的这篇文章主要介绍了整除分块，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

整除分块

整除分块是用来求这样的式子的：

(sum_{i=1}^{n}lfloordfrac k irfloor)

如果打出表会发现这个值是呈阶梯状下降的，然后他的取值最多有 (2sqrt n) 种，所以只要能 (O(1)) 求出每个块的右边界，就可以将这个 (O(n)) 的式子优化到 (O(sqrt n))。

---

(O(1)) 求右边界的方法：

设左端点为 (l)，(t=lfloordfrac k lrfloor)，

1. (tne0,r=min(lfloordfrac k trfloor,n))
2. (t=0,r=n)

---

证明：

先证明 (r=lfloordfrac k trfloor) 时，(lfloordfrac k {lfloorfrac k trfloor}rfloor) 大于等于 (t) 。

(t=lfloordfrac k lrfloorleqdfrac k l)

(lfloordfrac k {lfloorfrac k trfloor}rfloorgeqlfloordfrac k { frac k t}rfloor=t)

(lfloordfrac k {lfloorfrac k lrfloor}rfloorgeq t)

再证明 (r=lfloordfrac k trfloor+1) 时，(lfloordfrac k {lfloorfrac k trfloor+1}rfloor) 小于(t)，这样由 (lfloordfrac k irfloor) 单调不升且存在 (lfloordfrac k irfloor=t) 就可以得证 (r=lfloordfrac k trfloor) 时是最大的满足条件的右端点。

(lfloordfrac k {lfloorfrac k trfloor+1}rfloorleqdfrac k {lfloorfrac k trfloor+1})

只需证 (dfrac k {lfloorfrac k trfloor+1}<t)

把分母乘过去，(k<t*{lfloorfrac k trfloor+t})

设 (k=x*t+r,0leq r<t)

则 (x*t+r<t*x+t)

有(r<t)

得证。

---

好像可以拓展到二维，但我还没看，先咕了

脚本宝典总结

以上是脚本宝典为你收集整理的整除分块全部内容，希望文章能够帮你解决整除分块所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。