参考:
整除分块 - 知乎
董晓算法 G33 整除分块(数论分块)
图都是摘的上面的。
整除分块
整除分块是数论中的一个知识点。一个整除式子在分母不固定的时候,得到的结果也有可能不同,但是因为是整除,所以分母在取连续的值的时候,算出的结果有可能是相同的。比如:
整除分块可以算出每段连续取值区间的左右端点。因为区间个数最多有 2 ∗ n 2*\sqrt n 2∗n 个,从而它可以 O ( n ) O(\sqrt n) O(n) 遍历整除式子的所有取值和取值区间。
分块的性质:
- 分块的块数 ≤ 2 n \le 2\sqrt{n} ≤2n(也就是连续的相同取值的区间个数最多只有 2 n 2\sqrt{n} 2n 个)。
证明:
向下取整
性质: i i i 所在块的右端点为 r = ⌊ n ⌊ n i ⌋ ⌋ r=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor r= ⌊in⌋n 。
- 证明:
我们通过这个性质可以用区间左端点算出右端点,通过右端点又可以得到下一段区间的左端点,循环下去就可以遍历所有区间(块)了。
code:
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
...
}
向上取整:
向上取整有两种遍历方式,一个是从前向后( 1 → n 1\rightarrow n 1→n),另一个是从后向前( n → 1 n\rightarrow 1 n→1)。前者比较符合我们的直观思路,后者和前面的向下取整的过程高度对称,写法比较简洁。先说后者:
从后向前遍历:
性质: i i i 所在块的左端点为 l = ⌈ n ⌈ n i ⌉ ⌉ l=\left\lceil\dfrac{n}{\left\lceil\dfrac{n}{i}\right\rceil}\right\rceil l= ⌈in⌉n 。
- 证明是类似的:
i i i 所在块的值 k = ⌈ n i ⌉ k=\left\lceil\dfrac{n}{i}\right\rceil k=⌈in⌉,则 k ≥ n i k\ge \dfrac{n}{i} k≥in,则 ⌈ n k ⌉ ≤ ⌈ n n i ⌉ = ⌈ i ⌉ = i \left\lceil\dfrac{n}{k}\right\rceil\le\left\lceil\dfrac{n}{\dfrac{n}{i}}\right\rceil=\left\lceil{i}\right\rceil=i ⌈kn⌉≤ inn =⌈i⌉=i
所以 i m i n = ⌈ n k ⌉ = ⌈ n ⌈ n i ⌉ ⌉ i_{min}=\left\lceil\dfrac{n}{k}\right\rceil=\left\lceil\dfrac{n}{\left\lceil\dfrac{n}{i}\right\rceil}\right\rceil imin=⌈kn⌉= ⌈in⌉n 。代码实现时,左端点 k = ( n + r − 1 ) / r , l = ( n + k − 1 ) / k k=(n+r-1)/r,l=(n+k-1)/k k=(n+r−1)/r,l=(n+k−1)/k
同样的方法进行遍历,不过由于是从右端点算左端点,所以方向变成从后向前遍历了。
code:
for(int l,r=n,k;r>=1;r=l-1){
k=(n+r-1)/r;
l=(n+k-1)/k;
...
}
从前向后遍历:
性质: i i i 所在块的右端点为 r = ⌊ n − 1 ⌊ n + i − 1 i ⌋ − 1 ⌋ r=\left\lfloor\dfrac{n-1}{\left\lfloor\dfrac{n+i-1}{i}\right\rfloor-1}\right\rfloor r= ⌊in+i−1⌋−1n−1 。
-
证明1:
{ k = ⌈ n i ⌉ = ⌊ n + i − 1 i ⌋ r = m a x ( i ) , i k ≤ n + i − 1 ⇒ r = ⌊ n − 1 ⌊ n + i − 1 i ⌋ − 1 ⌋ \begin{equation*} \begin{cases} k = \left\lceil\dfrac{n}{i}\right\rceil =\left\lfloor\dfrac{n+i-1}{i}\right\rfloor \\ r=max(i),ik\le n+i-1 \end{cases} \end{equation*}\Rightarrow r=\left\lfloor\dfrac{n-1}{\left\lfloor\dfrac{n+i-1}{i}\right\rfloor-1}\right\rfloor ⎩ ⎨ ⎧k=⌈in⌉=⌊in+i−1⌋r=max(i),ik≤n+i−1⇒r= ⌊in+i−1⌋−1n−1 -
证明2:
因为 k = ⌈ n i ⌉ k=\left\lceil\dfrac{n}{i}\right\rceil k=⌈in⌉,所以 i ( k − 1 ) < n ≤ i k i(k-1)\lt n\le ik i(k−1)<n≤ik n k ≤ i < n k − 1 \dfrac{n}{k}\le i\lt \dfrac{n}{k-1} kn≤i<k−1n因为 i i i 是整数 ⌈ n k ⌉ ≤ i ≤ ⌊ n − 1 k − 1 ⌋ \left\lceil\dfrac{n}{k}\right\rceil\le i\le \left\lfloor\dfrac{n-1}{k-1}\right\rfloor ⌈kn⌉≤i≤⌊k−1n−1⌋根据上面的式子,显然 r = i m a x = ⌊ n − 1 k − 1 ⌋ = ⌊ n − 1 ⌊ n + i − 1 i ⌋ − 1 ⌋ r=i_{max}=\left\lfloor\dfrac{n-1}{k-1}\right\rfloor=\left\lfloor\dfrac{n-1}{\left\lfloor\dfrac{n+i-1}{i}\right\rfloor-1}\right\rfloor r=imax=⌊k−1n−1⌋= ⌊in+i−1⌋−1n−1
code:
for(int l=1,r,k;r<=n;l=r+1){
k=(n+l-1)/l;
r=(n-1)/(k-1);
...
}