整除分块学习笔记
xuchuhan
·
·
算法·理论
前言
本文是作者学习整除分块后的一些心得，可能有所不足，如有错误，望读者指正。
分块技巧
本文以求解问题：
\sum_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor
为例讲述整除分块。
易知当 \left\lfloor\dfrac{n}{i}\right\rfloor=d 且 n,d 一定时，i 的取值范围是一段连续的区间，记作 [L,R]。
假设 L 一定，如何快速求出 R 呢？
令 \left\lfloor\dfrac{n}{L}\right\rfloor=d，求最大的 \Delta，此时 R=L+\Delta 且 \left\lfloor\dfrac{n}{L}\right\rfloor=\left\lfloor\dfrac{n}{L+\Delta}\right\rfloor=d。
将两个式子化为整式可得 Ld+r_1=(L+\Delta)d+r_2=n，其中 0\leq r_1,r_2<d。两式相减得 \Delta d=r_1-r_2。
\because \Delta d=r_1-r_2
\therefore r_2=r_1-\Delta d
又 \because r_2\geq0
\therefore r_1\geq\Delta d
\therefore \Delta\leq\left\lfloor\dfrac{r1}{d}\right\rfloor
又 \because r_1=n \bmod L=n-L\times\left\lfloor\dfrac{n}{L}\right\rfloor,d=\left\lfloor\dfrac{n}{L}\right\rfloor
\therefore \Delta\leq\left\lfloor\dfrac{n-L\times\left\lfloor\dfrac{n}{L}\right\rfloor}{\left\lfloor\dfrac{n}{L}\right\rfloor}\right\rfloor
\therefore \Delta_{\max}\\=\left\lfloor\dfrac{n-L\times\left\lfloor\dfrac{n}{L}\right\rfloor}{\left\lfloor\dfrac{n}{L}\right\rfloor}\right\rfloor\\=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{L}\right\rfloor}\right\rfloor-L
\therefore R=L+\Delta_{\max}=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{L}\right\rfloor}\right\rfloor
然后 L 的初始值从 1 开始，R 根据 L 推导，接着之后的 L=R+1。
显然当 L\leq \sqrt{n} 时 L 有 不超过\sqrt{n} 种取值，当 L>\sqrt{n} 时 \dfrac{n}{L} 不超过有 \sqrt{n} 种取值，所以 L 共有不超过 2\sqrt{n} 种取值，加上 L,R 的计算均为 \mathcal{O(1)} 级别的，所以整个算法的时间复杂度就是 \mathcal{O(\sqrt{n})}，算是较为优秀的了。
例题
P2261 [CQOI2007] 余数求和
简单推导即可：
用等差数列结合整除分块做即可。
$\text{code}$:
```cpp
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,k,L=1,R,ans;
signed main(){
cin>>n>>k,ans=n*k;
while(L<=n){
if(k/L>0)R=min(k/(k/L),n);
else R=n;//跳右端点
ans-=(R-L+1)*(L+R)/2*(k/L),L=R+1;//等差数列求和
}
cout<<ans;
return 0;
}
```
### [P6583 回首过去](https://www.luogu.com.cn/problem/P6583)
非常有学习意义的一题。
考虑将 $\dfrac{x}{y}$ 转化为 $\dfrac{b\times c}{a\times c}$，其中 $a$ 只包含因数 $2,5$ 且 $\gcd(c,10)=1$。
我们考虑枚举合法的 $c$ 并求出同样合法的 $a,b$ 的情况数。
显然 $c \in [1,n]$ 且 $\gcd(10,c)=1$ 时，$b\in[1,\lfloor\frac{n}{c}\rfloor]$，而 $a$ 则可以是 $[1,\lfloor\frac{n}{c}\rfloor]$ 中只含因数 $2,5$ 的数，将所有合法的情况数记为 $f(\lfloor\frac{n}{c}\rfloor)$。
故总答案为 $f(\lfloor\frac{n}{c}\rfloor)\times \lfloor\frac{n}{c}\rfloor$ 乘上 $c$ 的取值方案数。
但 $n\leq10^{12}$，显然，这个算法还是不够优秀。
等等，$\left\lfloor\frac{n}{c}\right\rfloor$，这个不是整除分块吗？我们显然可以求出 $[L,R]$ 使得 $\lfloor\frac{n}{L}\rfloor=\lfloor\frac{n}{R}\rfloor=k$，那么时间复杂度不就降至 $\sqrt{n}$ 级别了吗？
但是还有问题，我们无法直接通过 `c%2!=0&&c%5!=0` 判断 $c$ 是否合法了。
那怎么办？通过容斥原理可以解决。
$[L,R]$ 中合法的 $c$ 可以这样计算：$[L,R]$ 中 $1$ 的倍数 $-$ $[L,R]$ 中 $2$ 的倍数 $-$ $[L,R]$ 中 $5$ 的倍数 $+$ $[L,R]$ 中 $10$ 的倍数，记为 $f'([L,R])$。
但是这样的函数并不是很好求。但是将 $f'([L,R])$ 换一种形式，变为 $f'([1,R])-f'([1,L])$ 就可以通过除法直接求得了。
所以问题就迎刃而解了。
$\text{code}$：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,L=1,res;
int g1(int x){return x-x/2-x/5+x/10;}//求c的取值方案数
int g2(int x){//求1~c内a的取值方案数
int ans=0;
for(int i=1;i<=x;i<<=1)for(int j=i;j<=x;j*=5)ans++;
return ans;
}
signed main(){
cin>>n;
while(L<=n){
int R=n/(n/L);
res+=(g1(R)-g1(L-1))*g2(n/L)*(n/L),L=R+1;
}
cout<<res;
return 0;
}
```