题目分析
本题为博弈论问题，涉及两个玩家轮流从木头长度中减去一个质数。无法操作者输。
错误解法：贪心
参照类似周赛题目的思路，尝试让一方稳赢，即每次砍最多的质数。采用埃氏筛快速找到小于当前木头长度的最大质数，快速降到 0 或 1。
错误原因：
- 局部最优≠全局最优：3828 题贪心正确是因为先手有绝对控制权，而此题并非真正的博弈，本质是找数组首尾最大值（类比）。
- 反例：拿 n=15 举例。
- 贪心时：小蓝选最大质数 13，剩 15-13=2，小乔选 2→小蓝选了最大质数 13，小蓝却输了。
- 不贪心时：小蓝选质数 5，剩 15-5=10。后续无论小乔怎么选，小蓝均有必胜策略。
因此贪心在此题是错误的。
正确解法：动态规划
时间复杂度：O(MAX_N + T)
①状态表示： dp[x] = 1：先手必胜 dp[x] = 0：先手必败
②状态转移方程： 只要存在一个质数 p，让对手面对 x-p 时处于必败态，此玩家就可以选这个 p 来赢→dp[x]=1。 如果所有质数 p 都会让对手进入必胜态，当前玩家无论怎么选都输→dp[x]=0。
③初始化： dp[0]=0, dp[1]=0。 当长度为 0 或 1 时，无法进行任何砍柴操作，当前玩家直接输 → 必败态。
④填表顺序： 从左往右。
⑤返回值： 对于输入的木头长度 n，直接返回预处理好的 dp[n]： 若 dp[n] = 1 → 小蓝（先手）赢 若 dp[n] = 0 → 小乔（后手）赢
素数筛选：欧拉筛
使用欧拉筛（线性筛）算法生成质数表，保证线性复杂度 O(N)。
①初始化： 用布尔数组 isprime[] 标记每个数是否为质数。 初始时全部设为 true，再将 0 和 1 标记为 false。 用列表 primes 存储所有筛出的质数。
②遍历每个数 i（从 2 到 MAX_N）： 若 isprime[i] 为 true，说明 i 是质数，将其扔进 primes。 遍历已筛出的所有质数 p：
- 若 i * p 超过 MAX_N，直接终止循环，避免溢出。
- 标记 isprime[i*p] = false，p 的 i 倍都不是质数。
- 优化：若 i % p == 0，立即终止循环。避免重复筛除，保证每个合数只被最小质因子标记一次。
Java 代码实现
错误解法：贪心
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
[] ret = [n];
( ; i < n; i++) {
sc.nextInt();
;
(a >= ) {
a -= prime(a);
cnt++;
}
(cnt % != ) ret[i] = ;
}
( ; i < n; i++) System.out.println(ret[i]);
sc.close();
}
{
[] isprime = [n + ];
( ; i <= n; i++) isprime[i] = ;
( ; i <= n; i++) {
(isprime[i]) {
( i * i; j <= n; j += i)
isprime[j] = ;
}
}
( n; i >= ; i--)
(isprime[i]) i;
-;
}
}
