题目 3224: 蓝桥杯2024年第十五届省赛真题-砍柴
时间限制: 3s 内存限制: 512MB 
题目描述
小蓝和小乔正在森林里砍柴，它们有 T 根长度分别为 n1, n2, · · · , nT 的木头。对于每个初始长度为 n 的木头，小蓝和小乔准备进行交替砍柴，小蓝先出手。每次砍柴时，若当前木头长度为 x ，需要砍下一截长度为 p 的木头，然后换另一个人继续砍，其中 2 ≤ p ≤ x 且 p 必须为质数。当轮到某一方时 x = 1 或x = 0 ，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每根木头判断是小蓝赢还是小乔赢，如果小蓝赢请输出 1 （数字 1），如果小乔赢请输出 0 （数字 0）。

输入格式
输入的第一行包含一个正整数 T，接下来 T 行，每行包含一个正整数，其中第 i 的整数为 ni 。

输出格式
输出 T 行，每行包含一个整数，依次表示对于每一根木头的答案。

样例输入复制
3
1
2
6
样例输出复制
0
1
1
提示
【样例说明】

对于 n1 = 1 ，由于当前长度 x = 1 ，小蓝直接输掉，小乔赢；

对于 n2 = 2 ，小蓝选择 p = 2 ，轮到小乔时当前长度 x = 2 − 2 = 0 ，小乔输掉，小蓝赢；

对于 n3 = 6 ，小蓝选择 p = 5 ，轮到小乔时 x = 6 − 5 = 1 ，小乔输掉，小蓝赢。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ ni ≤ 103；对于所有评测用例，1 ≤ ni ≤ 105 ，1 ≤ T ≤ 104

1.分析

        1.我们知道0和1的长度是必输的长度，那么只要减去一个质数等于必输的长度，那么就必赢。

        2.反过来，我们减去一个必输的长度，如果得到的是一个质数，那么是必赢的。

        为什么要反过来呢，因为必输的长度比质数的数量要少，枚举的次数会变少，个人认为。

2.代码

        

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int MAX = 1e5 + 100;
int h[MAX], n;    //记录结果的数组
int a[MAX], num;  //存储必输的树木长度
int idx[MAX];     //标记数组，0  1 和非素数标记为1
int re[MAX], r;   //存储素数
int t[MAX];       //存储询问void init(int x) {idx[0] = 1;               //标记初始化，因为0和1不是素数idx[1] = 1;for (int i = 2; i <= x; i++) {if (!idx[i]) {     //是素数re[r++] = i;   //记录h[i] = 1;      //长度为素数，必赢}else {a[num++] = i;          //判断长度是否会输，先记录，如果不是再移除for (int j = 0; j < num-1; j++) {  //遍历必输的长度if (!idx[i - a[j]]) {       //如果减去必输的长度等于素数，这个长度必赢h[i] = 1, num--;break;}}}for (int j = 0; re[j] <= x / i; j++) {   //筛素数idx[re[j] * i] = 1;if (i % re[j] == 0) break;}}
}int main() {cin >> n;a[num++] = 0;         //初始化两个必输的长度a[num++] = 1;int x=0;for (int i = 0; i < n;i++) {   //输入cin >> t[i];x =max(x, t[i]);           //记录最大值，不然会超时}init(x); for (int i = 0; i < n; i++) {    //输出cout << h[t[i]] << endl;}return 0;
}