题解：CF2004E Not a Nim Problem

伊地知虹夏 · 2024-08-26 17:31:49 · 题解

笑点解析：(E + D) < B

发现每堆游戏是相对独立的，通过计算每堆的 Sprague-Grundy (SG) 值，然后将这些值进行异或运算，以判断当前状态是否为必胜（即结果是否为 0）。

接下来，我们需要探讨如何计算 SG 值。

通过观察前 30 个 SG 值，我们首先注意到偶数的 SG 值均为 0。此外，我们发现奇质数的 SG 值是连续的。进一步的观察揭示，合数的 SG 值等于其最小质因子的 SG 值。

证明：设 S_n = \{f(x) | (x,n) = 1\} 。

我们使用数学归纳法来推导，假设对于所有 n \leq k 的情况都成立，接下来看 n = k + 1 。

• 如果 n 是质数，由于所有小于或等于 k 的 x 都与 n 互质，因此 \operatorname{mex} S_n 将等于 \max \{f(x) | x \le k\} + 1。

• 如果 n 是合数，设其最小质因子为 p ，那么对于所有 x < p ，有 f(x) \in S_n 。同时，由于 p 是 x 的因子，满足 \gcd(n,x) > 1，所以 f(p) \notin S_n 。因此，\operatorname{mex} S_n = f(p)。

证明结论后，我们就可以使用线性筛法求出 SG 值。

接下来是我调校了很久后 GPT 3.5 给出的代码

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 10000000;  // 最大值为 10^7
int min_prime[MAXN + 1];    // 存储每个数的最小质因子
int sg[MAXN + 1];           // SG 值数组
vector<int> primes;         // 存储质数

// 线性筛法计算最小质因子和 SG 值
void calculate_min_prime_and_sg() {
  memset(min_prime, 0, sizeof(min_prime));  // 初始化最小质因子数组
  memset(sg, 0, sizeof(sg));                // 初始化 SG 值数组
  // 线性筛法
  for (int i = 2; i <= MAXN; ++i) {
    if (min_prime[i] == 0) {  // 如果 i 是质数
      min_prime[i] = i;       // 质数的最小质因子是它自己
      primes.push_back(i);    // 记录质数
      sg[i] = primes.size();
    }
    // 更新最小质因子
    for (int p : primes) {
      if (p > min_prime[i] || p * i > MAXN) break;  // 只需查找到 sqrt(i)
      min_prime[p * i] = p;                         // 设置最小质因子
    }
  }
  sg[1] = 1;  // SG(1) = 1
  sg[2] = 0;  // SG(2) = 0
  // 计算 SG 值
  for (int i = 3; i <= MAXN; ++i)
    if (min_prime[i] < i)
      sg[i] = sg[min_prime[i]];  // 合数的 SG 值等于其最小质因子的 SG 值
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // 预处理最小质因子和 SG 值
  calculate_min_prime_and_sg();

  int t;
  cin >> t;  // 测试案例的数量
  vector<string> results;

  while (t--) {
    int n;
    cin >> n;  // 当前测试案例的石头堆数量
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];  // 当前测试案例的石头数量
    }

    // 计算 SG 的异或值
    int xor_sum = 0;
    for (int num : a) {
      xor_sum ^= sg[num];  // 使用预处理的 SG 值
    }

    // 判断赢家
    if (xor_sum == 0) {
      results.push_back("Bob");
    } else {
      results.push_back("Alice");
    }
  }

  // 输出结果
  for (const string& result : results) {
    cout << result << "\n";
  }

  return 0;
}