自动搬运

查看原文

来自洛谷，原作者为

	0000pnc 几人仍眼睛明亮 几人已失了魂

搬运于2025-08-24 22:40:47，当前版本为作者最后更新于2022-10-24 18:37:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先注意到一个光源是亮着的，当且仅当其被改变状态的次数为奇数次。

对于一个数 $x$，如果操作次数足够多，它被改变状态的次数就是 $d(x)-1$，其中 $d(x)$ 是 $x$ 的正因子个数。

接下来我们来讨论这个足够多的操作次数的下限是多少。由于 $x$ 的最大正因子显然是它本身，所以这些操作应该至少改变到 $x$ 的倍数的状态，才能满足 $x$ 的正因子（除了 $1$）都被筛选过一遍（即：所有编号为 $x$ 的倍数的光源操作一次）

我们注意到 $l \lt r \lt n$。所以对于任意的 $i \in [l,r]$，我们都有 $i$ 被改变状态的次数为 $d(i)-1$。即 $i$ 如果是亮着的，那么 $d(i)$ 为偶数，即 $i$ 不为完全平方数。那么我们只用求出 $[l,r]$ 内的完全平方数个数即可。用 std::sqrt 可使复杂度变为 $O(\log r)$。