无忧seo_上海企业查询系统_推广普通话手抄报文字_seo能干一辈子吗

#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
vector<bool> p(N,true);
vector<int> a;
vector<int> f(N,0);void sieve(){for(int i=2;i<N;i++){if(p[i]){a.push_back(i);for(int j=i*2;j<N;j+=i){p[j]=false;}}}
}int main()
{sieve();for (int i = 2; i < N; i++) {for (int prime : a) {if (prime > i) break;  // 砍的木头不能比 n 还长if (f[i - prime] == 0 ) {f[i] = 1; // 先手能让对手进入 `输` 状态，则自己赢break;}}}int t;cin>>t;while(t--){int n;cin>>n;cout<<f[n]<<endl;}return 0;
}

 

博弈论

• f[n] = 1 表示 小蓝必赢（找到一个 p，使 f[n - p] = 0）
• f[n] = 0 表示 小蓝必输（所有 p 砍掉后，f[n - p] 全是 1，小乔必胜）

遍历所有质数 p，小蓝能选 p 使 f[n - p] = 0（对手输），则 f[n] = 1（自己赢）。

如果所有 p 都让对手 f[n - p] = 1（必赢），则 f[n] = 0（自己输）。