题解：P10584 [蓝桥杯 2024 国 A] 数学题

· · 题解

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

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

\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}) 的优秀复杂度。