整除分块

Glassy_Sky · 2023-04-03 19:31:44 · 个人记录

整除分块

在解决 {\sum \limits_{i=1}^{n} \lfloor \frac{n}{i} \rfloor } 这样的问题时，如果用暴力计算，效率显然是十分低下的。

所以这里引入整除分块算法，仅用 {O( \sqrt{n} )} 的复杂度。

下面以 {n=8} 为例。

观察上面第二行的值，发现是逐步变小的，而且是一段一段相等的数。

于是乎，为了快速求和，我们就给它一段一段求和。

即：数值 乘上 个数。

可以发现每一种值都是 {n} 的约数，所以这样的枚举不会超过 {2\sqrt{n}} 个，那么它的复杂度也就有了保证。

复杂度：{O(2\sqrt{n})}

参考代码：

long long get(long long n) {
    long long ans=0;
    for(long long l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans+=(r-l+1)*(n/l);
    }
    return ans;
}

证明：

先让 {l} 为分块的左边界，那么这块的单个值 {k= \lfloor \frac{n}{l} \rfloor} ，这样右边界 {r} 就是值为 {k} 的最大下标 {i} ，也就是说要找满足 {i \leqslant \frac{n}{k}} 的最大的 {i} ，即 {r=max(i)=\lfloor \frac{n}{k}} ，将 {k} 代入，得到 {r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor} 。