整除分块

常搭配莫反食用。莫比乌斯反演笔记

P2261 余数求和

求 \(\displaystyle\sum_{i=1}^n k\bmod i\)，\(n,k\le 1e9\)。

第一步：\(k\bmod i=k-i\cdot\lfloor\dfrac{k}{i}\rfloor\)，\(\text{原式}=\displaystyle\sum_{i=1}^nk-i\cdot[\frac{k}{i}]\).

第二步：\(\text{原式}=nk-\displaystyle\sum_{i=1}^ni\cdot[\dfrac{k}{i}]\)。

然后问题就是怎么求 \(\sum_{i=1}^ni\cdot [\dfrac{k}{i}]\) 了。

直接枚举肯定是不行的，但是 \([\dfrac{k}{i}]\) 只有 \(\sqrt k\) 种取值！

所以可以枚举 \([\dfrac{k}{i}]\) 的值。当这个值确定了，求出 \([\dfrac{k}{i}]\) 等于这个值的区间，然后在这个区间内就很简单了。

因为取值只有 \(\sqrt k\) 种，所以区间只有 \(\sqrt k\) 个。我们每个区间 \(O(1)\)，总复杂度就是 \(O(\sqrt k)\)。

怎么实现枚举取值？直接枚举又变成 \(O(k)\) 了，不行。

我们可以用类似双指针的方法，初始让指针 \(l=1\)，求出 \([\dfrac{k}{i}]\) 等于 \([\dfrac{k}{l}]\) 的最大的 \(i\)，令指针 \(r\leftarrow i\)。算完这段区间再令 \(l\leftarrow r+1\)，不断循环，直到 \(l\) 超过 \(n\)。

（一定要搞清楚 \(l\) 的上界，还有 \(r\) 是根据什么确定的！）

怎么求 \(r\)？令 \(p=[\dfrac{k}{l}]\)，\(l\) 已知，这是可以 \(O(1)\) 求出的。我们求出 \([\dfrac{k}{i}]=p\) 中 \(i\) 的范围，最大的 \(i\) 就是 \(r\) 。

\([\dfrac{k}{i}]=p\iff p\le \dfrac{k}{i}<p+1\iff \dfrac{k}{p+1}<i\le \dfrac{k}{p}\)。

那么最大的 \(i\) 就很显然是 \([\dfrac{k}{p}]\) 了，也就是 \(\lfloor\dfrac{k}{\lfloor\frac{k}{l}\rfloor}\rfloor\)。

以上就是所有思路，但是在代码上还有要注意的地方。

首先注意 k / (k / l) 的结果可能会超过 \(n\) 导致多算了一些东西，会 WA。所以要取 \(\min\)。

然后注意在 k / l = 0 的时候一定要跳出循环，不然上面 k / (k / l) 直接除 \(0\) 了。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, k;
ll ans = 0;

int main() {
    cin >> n >> k;
    ans = n * k;
    for (int l = 1, r = 0; l <= n; l = r + 1) {
        if (k / l != 0)
            r = min(k / (k / l), n);
        else
            break;
        ans -= 1ll * (k / l) * (l + r) * (r - l + 1) / 2;
    }
    cout << ans << endl;
    return 0;
}

整除分块一般用来处理 \([x]\) 的问题。