自动搬运

查看原文

来自洛谷，原作者为

	zhouyuhang Bénédiction de Dieu dans la solitude

搬运于2025-08-24 22:59:24，当前版本为作者最后更新于2024-06-18 22:59:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

现有的题解问题比较多，有必要写一篇题解说明。

略去简单推导，快进到所求：

$$\sum _ {k = 1} ^ n \mu ^ 2 (k) \left\lfloor \sqrt \frac {n} {k} \right\rfloor \left\lfloor \sqrt \frac {m} {k} \right\rfloor $$

（值得澄清的是，形如 $\lfloor \sqrt \frac {n} {k} \rfloor$ 的式子不同取值是 $\Theta (k ^ {1 / 3})$ 而非 $\Theta (k ^ {1 / 4})$ 的，这似乎是一个流传颇久的误区。证明只需以 $n ^ {1 / 3}$ 为阈值分别考虑即可）

整除分块，记 $\lfloor \sqrt \frac {n} {k} \rfloor = t$，反解得 $\lfloor \frac {n} {(t + 1) ^ 2} \rfloor < k \le \lfloor \frac {n} {t ^ 2} \rfloor$。于是我们只需对每个 $x = \lfloor \frac {n} {t ^ 2} \rfloor$ 或 $x = \lfloor \frac {m} {t ^ 2} \rfloor$ 求出 $\sum _ {k = 1} ^ x \mu ^ 2(k)$ 即可。

而

$$\begin{aligned} & \sum _ {k = 1} ^ x \mu ^ 2(x) \\ & = \sum _ {k = 1} \mu(k) \left\lfloor \frac {x} {k ^ 2} \right\rfloor \end{aligned} $$

上式极为经典，P4318，P9238 等均为其直接应用。同样记 $\lfloor \frac {x} {k ^ 2} \rfloor = t$ 可解得 $\lfloor \sqrt \frac {x} {t + 1} \rfloor < k \le \lfloor \sqrt \frac {x} {t} \rfloor$（很共轭，不是吗？），于是我们又只需对每个 $p = \lfloor \sqrt \frac {x} {t} \rfloor$ 求出：

$$\sum _ {k = 1} ^ p \mu(k)$$

这可以使用杜教筛解决。

接下来我们将选择阈值 $B$，预处理出 $B$ 以内 $\mu(x),\mu ^ 2(x)$ 的前缀和，这显然只需要 $O(B)$ 的时间。对于计算 $\sum _ {k = 1} ^ p \mu(k)$ 而言，其代价为 $O(p B ^ { - 1 / 2})$；从而对单个 $x$ 计算 $\sum _ {k = 1} ^ x \mu ^ 2 (k)$ 时，复杂度即为 $O(x B ^ {- 3 / 2})$；最终对每个 $x = \lfloor \frac {n} {t ^ 2} \rfloor$ 都求的时候，复杂度即 $O(n B ^ {- 3 / 2})$（以上省略若干积分）。

最终取 $B = O(n ^ {2 / 5})$ 可以得到 $O(n ^ {2 / 5})$ 的优秀复杂度。