济宁网站建设那家好,深圳做网站推广排名,苏小小移动网站,做音乐网站要注意什么质数与合数
题意#xff1a;
FFF和GGG正在玩一个质数与合数的游戏 一开始有N个石头 FFF和GGG轮流对这堆石头进行操作#xff0c;FFF每次选择1到K之间的一个数x#xff0c;并拿走x个石头#xff0c;拿走之后剩下的石头数量必须是质数 接着GGG进行同样的操作#xff0c;但…质数与合数
题意
FFF和GGG正在玩一个质数与合数的游戏 一开始有N个石头 FFF和GGG轮流对这堆石头进行操作FFF每次选择1到K之间的一个数x并拿走x个石头拿走之后剩下的石头数量必须是质数 接着GGG进行同样的操作但是要求拿走之后剩下的石头数量必须是合数 假设双方都足够聪明第一个不能操作的人输 以为到这里就结束了 显然一开始两人之间有一人知道自己有必胜策略现在他想要尽可能快的赢另外一个人则想要尽可能输的慢一点 给你N与K假设游戏最终持续了X轮如果FFF赢了输出X否则输出-X 注意1既不是质数也不是合数
题解
判断输赢很简单因为每次取数范围是[1,K]而FFF要每次取完都是质数如果存在两个相邻的质数差大于K1也就是无论取任何数都不可能剩下为质数那么FFF就输了反之FFF必胜因为FFF都能取到但是游戏到最后时剩下34,5GGG都会输,所以FFF必胜 本题麻烦在计算游戏会进行几轮 根据题意游戏的胜负从一开始就给定了但是赢的人想赶紧赢输的人想慢点输。如果是FFF输了保证GGG步骤最少呢么GGG每次都走到下一个素数的前一个的位置相当于故意恶心FFF让FFF正好错过自己的质数FFF就永远不能跳过相差大于k1的两个点。 就比如当前点是31K3轮到GGG了现在离30最近的质数是29GGG就走到28因为GGG不能走到质数让FFF错过自己的质数 如果是FFF赢了他想赶紧结束比赛就会尽可能跳更远的质数而GGG为了拖慢每次只会跳一个单位当然当跳到2,3时GGG就算输了不能再跳
代码
懒得写了官方代码但是我每句话做了详细注释
#include bits/stdc.h
using namespace std;
const int N1e75;int prime[N],cnt0;
bool st[N];void init()
{for(int i2;iN-5;i){if(!st[i]) {prime[cnt]i;}for(int j0;prime[j](N-5)/i;j){st[i*prime[j]]true;if(i%prime[j]0){break;}}}
}int main()
{init();bool flagtrue;int n,k,pos,m0;scanf(%d%d,n,k);if(n2) {puts(0);return 0;}for(int i1;prime[i]n;i){m;if(prime[i]-prime[i-1]k1)//如果有距离大于k1FFF就输了 {flagfalse;}}if(n-prime[m]k) {puts(0);return 0;}//如果第一步FFF都跳不了 if(flag)//FFF可以赢{// puts(9);//FFF可以赢,那么每次选k的时候会尽量多选些质数.int wz,ans0;while(1){wzn-k;int xblower_bound(prime,primem,wz)-prime;//找第一个大于等于wz的质数也就是离n最远的质数 ans;//FFF操作完毕 if(prime[xb]3) break;//如果当前点小于等于3GGG就输掉比赛 nprime[xb]-1;//GGG所跳点 ans;//GGG操作完毕 }printf(%d\n,ans);}else//GGG可以赢{// coutprime[pos]endl;int wz,ans0;int cntm;if(nprime[m])//如果起点就是质数 {if(nprime[m-1]k) cnt--;//如果第一步FFF可以走的话 else {puts(0);return 0;}}while(1){if(nprime[cnt]k)//如果FFF可以走 {nprime[cnt];//FFF走一步 }else break;ans;int wzn-k; int xbupper_bound(prime,primem,wz)-prime;//找第一个大于n-k的质数也就是离n最近的质数 nprime[xb]-1;//GG正好走到prime[xb]-1(也就是素数的前一个位置来恶心FFF) cntxb-1;//FFF下一个最近的质数是第xb-1位因为xb位被GGG给“完美错过” ans;}if(ans) printf(%d\n,-ans);else puts(0);}return 0;
}
