0%

整除分块

整除分块

指定$x$,求$\sum^{r}_{i=l}x/i$,可以使用分块优化。

其原理是此类式子中,i的每次变化不会让分式值立即改变。多个i会有一样的结果,而这个“次数”是可以直接计算的。
根据$\lfloor{ x \over b}\rfloor=a$推出$\lfloor{ x \over a}\rfloor=b$,当$b<a$,即此时b能唯一确定a,而当分子不断增大,b更大时,就会出现b增大,结果不变的情况,即一块的结果相同,这一块的结果值因为小,都映射到一个分子上去,这个分子是这块最后一个,即能整除的那个,而不是他们应该对应那个.
如对9:

1 2 3 4 5 6 7 8 9 10
9 4 3 2 1 1 1 1 1 0

可以推出,这个分子到结果的入射范围限制是分子小于sqrt(x)。

此后的项中,只有部分能从结果推分子,且为分块的最后一个。

满足互推,则可直接求:$\lfloor{ x \over {\lfloor {x \over b}\rfloor} } \rfloor$其中b是一个块的一个位置,此式子结果块最右的位置,其中$\lfloor{ x\over b}\rfloor$是此块的值。上例中,可以从5,6直接计算到9。

在一个从l到r的求和中,块可能不完整,需要处理好边界,左边不一定是最左,右边如果超过也不要算多。

以下有一例:cf1485c
其中有一分式求和,使用了分块优化。

1
2
3
4
5
6
7
8
9
10
11
12
ll now=div+2;
while(1){
if(x/now==0)break;
ll tmp=x/(x/now);
if(tmp>y+1){
ans+=(x/now)* (y+1-now+1);
break;
}else{
ans+=(x/now)*(tmp-now+1);
now=tmp+1;
}
}//分母是x,分子从div+2~y+1