数学、整除分块/数论分块

计算 $\sum\limits_{i=1}^{n} \left\lfloor \dfrac{n}{i} \right\rfloor$ 的值的常用手段是整除分块。

首先不同的 $\left\lfloor \dfrac{n}{i} \right\rfloor$ 的值的数量与 $\sqrt{n}$ 同阶，证明一下。

不大于 $\sqrt{n}$ 的整数 $i$ 有 $\sqrt{n}$ 个，所以对于这些 $i$ 而言 $\left\lfloor \dfrac{n}{i} \right\rfloor$ 的值至多有 $\sqrt{n}$ 个。对于大于 $\sqrt{n}$ 的整数 $i$，由于 $\left\lfloor \dfrac{n}{i} \right\rfloor$ 的值小于 $\sqrt{n}$ 所以不同的 $\left\lfloor \dfrac{n}{i} \right\rfloor$ 的值不超过 $\sqrt{n}$ 个。

证毕。

所以只要能快速枚举所有 $\left\lfloor \dfrac{n}{i} \right\rfloor$ 值相等的 $i$ 就可以 $O(\sqrt{n})$ 计算 $\sum\limits_{i=1}^{n} \left\lfloor \dfrac{n}{i} \right\rfloor$ 的值。

枚举满足 $\left\lfloor \dfrac{n}{l-1} \right\rfloor \neq \left\lfloor \dfrac{n}{l} \right\rfloor$ 的左端点 $l$，找满足 $\forall i \in [l,r] \cap \mathbb{Z},\left\lfloor \dfrac{n}{i} \right\rfloor = \left\lfloor \dfrac{n}{l} \right\rfloor$ 的最大的整数 $r$，考虑 $r$ 的性质 $\left\lfloor \dfrac{n}{r} \right\rfloor = \left\lfloor \dfrac{n}{l} \right\rfloor$ 且 $\left\lfloor \dfrac{n}{r+1} \right\rfloor \neq \left\lfloor \dfrac{n}{l} \right\rfloor$，转化得到 $n = r \times \left\lfloor \dfrac{n}{l} \right\rfloor + R_0 (R_0 < \left\lfloor \dfrac{n}{l} \right\rfloor)$ 且 $n < (r+1) \times \left\lfloor \dfrac{n}{l} \right\rfloor$ 最终得到 $r = \left\lfloor \dfrac{n}{\left\lfloor \dfrac{n}{l} \right\rfloor} \right\rfloor$，完成推导。

注意右端点 $r$ 不能超过 $n$，不然会错。

时间复杂度 $O(\sqrt{n})$。

long long H(long long n){
    long long l=1ll,r=1ll,ret=0ll;
    while(l<=n){
        r=min(n/(n/l),n);
        ret+=(r-l+1)*(n/l);
        l=r+1;
    }
    return ret;
}