自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 23:07:44，当前版本为作者最后更新于2024-12-28 13:29:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Preface

数论 / 筛法 / 时间复杂度计算

为了防止被一个 M 开头 n 结尾的管理员等因为各种稀奇古怪的原因随意打回这篇博客，标注一下：在 irris 评分系统里的评分为 $900$。

Solution

首先为了达成某个指定的灯的开关序列，由于第 $i$ 盏灯的状态只和编号 $\leq j$ 的圣诞老人有关，从小到大做就好了，例题是 分手是祝愿。

先假设所有圣诞老人都来了，那么根据经典结论，应该是所有编号 $k^2$ 形式的灯变暗。然后，我们又要做一些让编号 $k^2\ (k \geq 2)$ 的灯重新变亮的工作。

考虑仅翻转第 $t$ 盏灯的状态下，我们要翻转哪些圣诞老人的出现，事实上只需要所有 $mt \leq n$ 其中 $\mu(m) \neq 0$ 即可，证明依据 $\sum_{d \mid n} \mu(d) = [n = 1]$ 即可。

我们可以据此刻画每个圣诞老人会在什么时候被翻转。换句话说，现在只需要求

$$n - \sum_{i=2}^n [2 \mid \sum_{d = 2}^{\sqrt{n}} [d^2 \mid i \land \mu(\frac{i}{d^2}) \neq 0]] $$

$d^2 \mid i \land \mu(\frac{i}{d^2}) \neq 0$ 的条件事实上是极为苛刻的，因为这要求 $i = d^2 \prod p$（$p$ 是互不相同的素数）的形式，这其实也 唯一确定 了一个合法的 $d$！所以这样带来的贡献其实就是 $S(n/d^2)$，其中 $S(n) = \sum_{i=1}^n \mu^2(i) = \sum_{i=1}^{\sqrt{n}} \mu(i) \left\lfloor \frac{n}{i^2} \right\rfloor$，显然可以在 $\mathcal O(\sqrt{n})$ 时间复杂度内被计算。

又有

$$\int_{d=2}^{\sqrt{n}} \sqrt{\frac{n}{d^2}} = \sqrt{n}\int_{d=2}^{\sqrt{n}} \frac{1}{d} \in \mathcal O(\sqrt{n}\log n) $$

于是暴力做的时间复杂度仅有 $\mathcal O(\sqrt{n}\log n)$，可以通过。