自动搬运

查看原文

来自洛谷，原作者为

	残阳如血 人事已尽，天命难违

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

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

以下是正文

---

$\textbf{Solution}$

诈骗题。

---

非常重要的是，本题的 press 是递归定义的，与平常所做的完全平方数类型的开关灯题不同。

---

考虑 $a$ 的所有除自身以外的因数 $d$，参考 press 函数，容易发现对于每次对 $d$ 的修改后，必然会修改 $a$。

令 $\text{cnt}_i$ 表示 $i$ 被修改的次数，可以发现，

$$\text{cnt}_i=\sum\limits_{\mathclap{d\mid i\operatorname{and}d\not=i}}{\text{cnt}_d}+1 $$

特别地，这个加 $1$ 是因为遍历到 $d$​ 时，对此的修改。

---

容易发现，当 $\text{cnt}_i$​ 为奇数时，灯开；反之，灯灭。

• 当 $i=1$ 时，显然 $\text{cnt}_i=1$，灯开。

• 当 $i\in\mathbb{P}$ 时，$\text{cnt}_i=\text{cnt}_1+1=1+1=2$，灯灭。

• 当 $i$ 为合数时，使用数学归纳法：

  命题

  当 $i$ 为合数时，$\text{cnt}_i$ 为偶数。

  证明

  显然，$\text{cnt}_4=\text{cnt}_{1}+\text{cnt}_{2}+1=1+2+1=4$。

  假设当前已经处理到了合数 $t$，则 $\text{cnt}_t$ 为偶数。

  考虑 $t$ 的下一个合数 $p$，由于 $(t,p)$ 范围内的数都是质数，所以 $\text{cnt}_{t+1}=\text{cnt}_{t+2}=\cdots=\text{cnt}_{p-1}=2$。

  对于 $p$ 的不等于 $1$ 并且不等于 $p$ 的因数 $r_i$，易知 $\text{cnt}_{r_{i}}$ 为偶数，那么其和也是偶数。

  那么 $\text{cnt}_p=\text{cnt}_1+\sum\text{cnt}_{r_i}+1=1+\text{偶数}+1=\text{偶数}$​。

  故得证。

综上所述，灯开着当且仅当 $k=1$ 的情况。

$\textbf{Code}$

#include <bits/stdc++.h>

int main() {
  int T, n, k;
  for (std::cin >> T; T; --T) {
    std::cin >> n >> k;
    if (k ^ 1) puts("NO"); // k != 1
    else puts("YES"); // k == 1
  }
  return 0;
}