update:添加了数学公式markdown

洛谷博客地址：https://www.luogu.com.cn/blog/KingofNight/post-shuo-lun-zheng-shuo-fen-kuai-ji-yang-xi-zheng-ming

一.复杂度证明

引理一:对于任意一个正整数$x$,$[\frac

的种类的数量在$\sqrt$级

证明:将$d$分为小于等于$\sqrt\(与大于\)\sqrt$的两部分

1.当$d\leq\sqrt$时:

假设每个$[\frac]\(都不一样,最多也就\)\sqrt$个值

2.当$d>\sqrt$时:

\([\frac{x}{d}]<\sqrt{x}\)

∴$[\frac]\(的取值同样不超过\)\sqrt$个

∴个数在根号$x$级(不超过$2*\sqrt$)

即,整数分块的复杂度为$O(\sqrt)$

二.一堆引理及证明

引理二:对于所有使$[\frac

证明:假设不是连续区间,则一定存在一个$l<t<r$,

使得$[\frac]=[\frac]\(且\)[\frac]\neq[\frac]$

∵$t>l$

∴$[\frac]<[\frac]$

∵$t<r$

∴$[\frac]>[\frac]$

∵$[\frac]=[\frac]$

∴假设不成立

∴所有使$[\frac]=C$的$i$,其集合一定是一段连续的整数区间

引理三:对于所有使$[\frac

证明一:

∵$[l,r]\(内所有的数都可以使\)[\frac]=C$(定义)

∴$C=[\frac]$

小引理:$r=[\frac

一.证明$[\frac]=C$

令$A=[\frac{[\frac]}]=[\frac]$

所以$AC$可以表示为:

\(AC=x-k(0<=k<A,C)\)

∴$A=\frac$

∴$\frac=\frac\geq\frac=C$

假设$\frac\geq C+1$

∴$AC\leq x-A$

∵$AC=x-k$

又∵$k<A$

∴假设不成立

∴$\frac<C+1$

综上所述:\(C\leq \frac{x}{A}<C+1\)

∴$[\frac]=C$

二.证明$A$为最大的使$[\frac]=C$成立的数

令$AC=x-k(0\leq k<A,C)$

假设$A$不是最大令$[\frac]=C$成立的数,由引理二知:

$A+1$一定可以使$[\frac]=C$

∴$(A+1)*C=x-g(0\leq g<A,C)$

∴$AC+C=x-g$

又∵$AC=x-k$

∴$C=k-g$

∵$0\leq k,g<C$

∴假设不成立

∴命题得证

综上所述:$A=[\frac]\(是最大的令\)[\frac]=C$成立的数

∴$A$满足r的所有性质

∴$r=A$即$r=[\frac]=[\frac{[\frac]}]$

∴引理三得证

三.实现方法

由引理三知,我们只需要知道$l$就可以$O(1)\(算出区间\)[l,r]\(使得对于\)\forall i\in [l,r]\(都有\)[\frac]=[\frac]\(且对于\)\forall i\notin [l,r]\(都有\)[\frac]\neq[\frac]$

而,如果我们要枚举区间$[L,R]$的所有整数,那么第一个区间的$l$一定是$L$!

那么之后的区间呢?

不就是前一个区间的"\(r\)"加个一嘛!

∴我们就可以在$\sqrt$枚举完整个区间了！

PS:一个区间的定义:具有一个范围[l,r],且满足对于$\forall i\in [l,r]\(都有\)[\frac]=[\frac]\(且对于\)\forall i\notin [l,r]\(都有\)[\frac]\neq[\frac]$