update:添加了数学公式markdown
洛谷博客地址：https://www.luogu.com.cn/blog/KingofNight/post-shuo-lun-zheng-shuo-fen-kuai-ji-yang-xi-zheng-ming
一.复杂度证明
引理一:对于任意一个正整数(x),([frac{x}{d}](1leq dleq x))
的种类的数量在(sqrt{x})级
证明:将(d)分为小于等于(sqrt{x})与大于(sqrt{x})的两部分
1.当(dleqsqrt{x})时:
假设每个([frac{x}{d}])都不一样,最多也就(sqrt{x})个值
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}] eq[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}geqfrac{Cx}{x}=C)
假设(frac{x}{A}geq C+1)
∴(ACleq x-A)
∵(AC=x-k)
又∵(k<A)
∴假设不成立
∴(frac{x}{A}<C+1)
综上所述:(Cleq frac{x}{A}<C+1)
∴([frac{x}{A}]=C)
二.证明(A)为最大的使([frac{x}{i}]=C)成立的数
令(AC=x-k(0leq k<A,C))
假设(A)不是最大令([frac{x}{i}]=C)成立的数,由引理二知:
(A+1)一定可以使([frac{x}{i}]=C)
∴((A+1)*C=x-g(0leq g<A,C))
∴(AC+C=x-g)
又∵(AC=x-k)
∴(C=k-g)
∵(0leq 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 iin [l,r])都有([frac{x}{i}]=[frac{x}{l}])且对于(forall i otin [l,r])都有([frac{x}{i}] eq[frac{x}{l}])
而,如果我们要枚举区间([L,R])的所有整数,那么第一个区间的(l)一定是(L)!
那么之后的区间呢?
不就是前一个区间的"(r)"加个一嘛!
∴我们就可以在(sqrt{x})枚举完整个区间了！
PS:一个区间的定义:具有一个范围[l,r],且满足对于(forall iin [l,r])都有([frac{x}{i}]=[frac{x}{l}])且对于(forall i otin [l,r])都有([frac{x}{i}] eq[frac{x}{l}])