数论分块

富比尼定理

用两种不同的方法计算同一个量，从而建立相等关系。

引理1

$\lfloor \dfrac{a}{bc} \rfloor = \lfloor \dfrac{\lfloor \dfrac{a}{b}\rfloor}{c} \rfloor$

引理2

$| \{\ \lfloor \dfrac{n}{d} \rfloor\ |\ d\in N_+, d \leq n\ \}| \leq \lfloor 2\sqrt{n} \rfloor$

当 $d \leq \lfloor \sqrt{n} \rfloor$ 时，有 $\lfloor \sqrt{n} \rfloor$ 种取值
当 $d > \lfloor \sqrt{n} \rfloor$ 时，有 $\lfloor \sqrt{n} \rfloor$ 种取值

数论分块结论

向下取整的数论分块

对于常数 $n$

成立且满足 $i \leq j \leq n$ 的 $j$ 的最大值为 $\lfloor \dfrac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$ ，即 $\lfloor \dfrac{n}{i} \rfloor$ 所在块的右端点为 $\lfloor \dfrac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$

向上取整的数论分块

成立且满足 $i \leq j \leq n$ 的 $j$ 的最大值为 $\lfloor \dfrac{n-1}{\lfloor \frac{n-1}{i} \rfloor} \rfloor$ ，即 $\lfloor \dfrac{n}{i} \rfloor$ 所在块的右端点为 $\lfloor \dfrac{n-1}{\lfloor \frac{n-1}{i} \rfloor} \rfloor$

$N$ 维数论分块

求含有 $\lfloor \dfrac{a_1}{i} \rfloor、\lfloor \dfrac{a_1}{i} \rfloor 、\lfloor \dfrac{a_1}{i} \rfloor \dots$ 的和式的数论分块，呢么右端点就会变成 $min_{j = 1}^{n}\{\dfrac{a_j}{ \lfloor \dfrac{a_j}{i} \rfloor}\}$