整除分块
指定$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 | ll now=div+2; |