一.复杂度证明
引理一:对于任意一个正整数x,[\frac{x}{d}](1\leq d\leq x)
的种类的数量在\sqrt{x}级
证明:将d分为小于等于\sqrt{x}与大于\sqrt{x}的两部分
1.当d\leq\sqrt{x}时:
假设每个[\frac{x}{d}]都不一样,最多也就个值
2.当d>\sqrt{x}时:
[\frac{x}{d}]<\sqrt{x}
∴[\frac{x}{d}]的取值同样不超过\sqrt{x}个
∴个数在根号x级(不超过2*\sqrt{x})
即,整数分块的复杂度为O(\sqrt{x})
二.一堆引理及证明
引理二:对于所有使[\frac{x}{i}]=C的i,其集合一定是一段连续的整数区间
证明:假设不是连续区间,则一定存在一个l<t<r,
使得[\frac{x}{l}]=[\frac{x}{r}]且[\frac{x}{l}]\neq[\frac{x}{t}]
∵t>l
∴[\frac{x}{t}]<[\frac{x}{l}]
∵t<r
∴[\frac{x}{t}]>[\frac{x}{r}]
∵[\frac{x}{l}]=[\frac{x}{r}]
∴假设不成立
∴所有使[\frac{x}{i}]=C的i,其集合一定是一段连续的整数区间
引理三:对于所有使[\frac{x}{i}]=C的i,如果其集合为[l,r],那么我们只需要知道l,就可以求出C和r
证明一:
∵[l,r]内所有的数都可以使[\frac{x}{i}]=C(定义)
∴C=[\frac{x}{l}]
小引理:r=[\frac{x}{[\frac{x}{l}]}]
一.证明[\frac{x}{A}]=C
令A=[\frac{x}{[\frac{x}{l}]}]=[\frac{x}{C}]
所以AC可以表示为:
AC=x-k(0<=k<A,C)
∴A=\frac{x-k}{C}
∴\frac{x}{A}=\frac{Cx}{x-k}\geq\frac{Cx}{x}=C
假设\frac{x}{A}\geq C+1
∴AC\leq x-A
∵AC=x-k
又∵k<A
∴假设不成立
∴\frac{x}{A}<C+1
综上所述:C\leq \frac{x}{A}<C+1
∴[\frac{x}{A}]=C
二.证明A为最大的使[\frac{x}{i}]=C成立的数
令AC=x-k(0\leq k<A,C)
假设A不是最大令[\frac{x}{i}]=C成立的数,由引理二知:
A+1$一定可以使$[\frac{x}{i}]=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{x}{C}]是最大的令[\frac{x}{i}]=C成立的数
∴A满足r的所有性质
∴r=A即r=[\frac{x}{C}]=[\frac{x}{[\frac{x}{l}]}]
∴引理三得证
三.实现方法
由引理三知,我们只需要知道l就可以O(1)算出区间[l,r]使得对于\forall i\in [l,r] 都有[\frac{x}{i}]=[\frac{x}{l}]且对于\forall i\notin [l,r]都有[\frac{x}{i}]\neq[\frac{x}{l}]
而,如果我们要枚举区间[L,R]的所有整数,那么第一个区间的l一定是L!
那么之后的区间呢?
不就是前一个区间的"r"加个一嘛!
∴我们就可以在\sqrt{x}枚举完整个区间了！
PS:一个区间的定义:具有一个范围[l,r],且满足对于\forall i\in [l,r] 都有[\frac{x}{i}]=[\frac{x}{l}]且对于\forall i\notin [l,r]都有[\frac{x}{i}]\neq[\frac{x}{l}]