[数学]除法分块

在数学中，我们有时需要求形如这样的式子： $$\sum_{i=1}^{n}f(\lfloor \frac {k} {i} \rfloor)$$ 如果我们正常的来计算，其时间复杂度为$O(n)$，但有没有更优秀的算法呢$qwq$ 不妨来看一道例题：[P2261 [CQOI2007]余数求和](https://www.luogu.org/problemnew/show/P2261) 题目大意，求$\sum _{i = 1}^{n} ({k\,mod\,i})$ 根据模的定义，有：$a\,mod\,b = a - b \times \lfloor \frac {a} {b} \rfloor$ 转化一下即求： $$\sum _{i = 1}^{n} ({k\,mod\,i}) = \sum _{i = 1}^{n} ({k - i \times \lfloor \frac {k} {i} \rfloor}) = n \times k - \sum_{i = 1}^{n} ({i \times \lfloor \frac {k} {i} \rfloor})$$ 故直接考虑求$\sum_{i = 1}^{n} ({i \times \lfloor \frac {k} {i} \rfloor})$的值即可…… 打表后发现，$\lfloor \frac {k} {i} \rfloor$在一定区域内相等，不妨考虑枚举区间分块。 设枚举到区间的左端点为$L$，右端点为$R$，$t = \lfloor \frac {k} {L} \rfloor$，且$\forall i \in [L, R]$，均满足$\lfloor \frac {k} {i} \rfloor = t$，欲求本块右端点$R$ 通过打表又发现，$R = \lfloor \frac {k} {t} \rfloor$，我们来严谨证明一下： 对于任意两个正整数$a, b$显然有$\lfloor \frac {a} {b} \rfloor \leq \frac {a} {b}$，$\frac {a} {b} - \lfloor \frac {a} {b} \rfloor < 1$故： $\because \lfloor \frac {k} {t} \rfloor \leq \frac {k} {t}$ $\therefore \frac {k} {\lfloor \frac {k} {t} \rfloor} \geq \frac {k} {\frac {k} {t}} = t$ $\therefore \lfloor \frac {k} {R} \rfloor = \lfloor \frac {k} {\lfloor \frac {k} {t} \rfloor} \rfloor \geq t$ $\because 0 \leq \frac {k} {t} -\lfloor \frac {k} {t} \rfloor < 1 $ $\therefore \frac {k} {t} < \lfloor \frac {k} {t} \rfloor + 1$ $\therefore \lfloor \frac {k} {R + 1} \rfloor = \lfloor \frac {k} {\lfloor \frac {k} {t} \rfloor + 1} \rfloor \leq \frac {k} {\lfloor \frac {k} {t} \rfloor + 1} < \frac {k} {\frac {k} {t}} = t$ 即$\lfloor \frac {k} {R} \rfloor = t, \lfloor \frac {k} {R + 1} \rfloor \neq t$，从而可知$R = \lfloor \frac {k} {t} \rfloor$为本块的右端点。 故如果一个块的左端点为$L$，$t = \lfloor \frac {k} {L} \rfloor$，且$\forall i \in [L, R]$，均满足$\lfloor \frac {k} {i} \rfloor = t$时，那么其右端点为$\lfloor \frac {k} {t} \rfloor$ 则在计算时可以从$1$枚举$L$，并计算出本块右端点$R$，设$t = \lfloor \frac {k} {L} \rfloor$，则对于当前块来说，其和为： $$\sum_{i = L}^{R} ({i \times \lfloor \frac {k} {i} \rfloor}) = \sum_{i = L}^{R} ({i \times t}) = t \times \sum_{i = L}^{R} i$$ 由于$\sum_{i = L}^{R} i = \frac {(L + R)(R - L + 1)} {2}$（等差数列求和） 故每块的和为$t \times \frac {(L + R)(R - L + 1)} {2}$，统计完一块的和后，令$L = R + 1$，继续统计下一块，像这样依次统计每块答案即可（但本题需注意边界问题，由于重点不在这里，故不再赘述） 考虑其时间复杂度： 由于$\lfloor \frac {k} {i} \rfloor$的取值不超过$\sqrt {k}$ 种： 当$i \leq \sqrt{k}$时，因为$i$最多有$\sqrt {k}$种取值，故$\lfloor \frac {k} {i} \rfloor$最多也只有$\sqrt {k}$种取值； 当$i > \sqrt {k}$时，则$\lfloor \frac {k} {i} \rfloor < \sqrt{k}$，故仍最多有$\sqrt{k}$种取值。 故其时间复杂度为$O(\sqrt{k})$