题解：P10565 [ICPC2024 Xi'an I] Chained Lights

残阳如血 · 2024-07-24 18:08:17 · 题解

\textbf{Solution}

诈骗题。

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

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

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

特别地，这个加 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;
}