有点菜，现在才会。
之前好多篇都烂尾了，这篇不能了。
数论分块往往适合于带有向下取整的题目，即求 \(\sum f(i)g(\lfloor\frac{n}{i}\rfloor)\) 的值。
当经过某些处理后可以 \(O(1)\) 求出 \(f(r)-f(l)\) 的值时，数论分块可以 \(O(\sqrt{n})\) 求出上述式子的值。
向下取整
\(\lfloor a \rfloor\) 等于不超过 \(a\) 的最大整数，即 \(a=b+r(0\le r<1)\) 中 \(b\) 的值。
引理1
对于 \(a,b,c\in\mathbb{Z}\)，\(\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor\)，交换 \(bc\) 同理。
证明
令 \(\frac{a}{b}=\lfloor\frac{a}{b}\rfloor+r(0\le r<1)\)。
\(\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{a}{b}\times\frac{1}{c}\rfloor=\lfloor(\lfloor\frac{a}{b}\rfloor+r)\times\frac{1}{c}\rfloor=\lfloor\frac{\lfloor{a}{b}\rfloor}{c}+\frac{r}{c}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor\)。
利用到了 \(\lfloor\frac{x+r}{c}\rfloor=\lfloor\frac{x}{c}\rfloor\)，其中 \(x,r,c\in\mathbb{Z}\)，\(0\le c<1\)。证明考虑讨论 \(x\) 和 \(c\) 的正负。