数论分块

数论分块

对于含有除法向下取整的式子，可以使用数论分块，将 \(\left \lfloor \frac{n}{i} \right \rfloor\) 相同的数统一计算。

使式子 \(\left \lfloor \frac{n}{i} \right \rfloor = \left \lfloor \frac{n}{j} \right \rfloor\) 满足 \(i<=j<=n\) 的最大的 \(j\) 为 \(\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor} \right \rfloor\) ，即 \(\left \lfloor \frac{n}{i} \right \rfloor\) 所在块的右端点。

for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    /*进行对(l,r)区间内答案的计算*/
}