浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛-D 涛涛和策策的游戏（尼姆博弈）

浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛-D 涛涛和策策的游戏

链接：https://ac.nowcoder.com/acm/contest/7872/D
来源：牛客网

题目描述
涛涛和策策打码累了的时候会聚在一起van游戏。
某一天他们又凑在一起玩游戏了，因为最近他们在学数学知识，所以就开始van博弈小游戏了。
他们写下n个数字，从策策开始两个人轮流进行操作，每次操作只能选择一个大于1的数字x，选择x的一个大于1的因数y，让x变为x/y。
谁先不能操作谁就输了。现在你需要判断出是哪个学长赢了游戏。
如果是策策赢了，输出"CC yyds!"
如果是涛涛赢了，输出"TT txdy!"
输入描述:
第一行一个整数n，代表写下了n个数字。（1≤n≤1×105）
第二行为用空格隔开的n个数字ai代表写下的n个数字。（1≤ai≤1×106）
输出描述:
输出"CC yyds!“或者"TT txdy!”
示例1
输入
复制
3
1 1 1
输出
复制
TT txdy!
示例2
输入
复制
3
2 2 2
输出
复制
CC yyds!

***思路***一看到题目，就很明显的感受出来这是一道博弈论，然后仔细一看，就会发现这是一道抽象化的尼姆博弈。我们只要把每个数分解成不能再拆解的质因数，那实际上每个数的质因数数量就相当于是这堆这堆石头中有几个石子，这时我们就发现这就是最经典的尼姆博弈，只要求所有堆的石子的数量异或就好了，结果是1先手必赢。

尼姆博弈的详情可以去百度一下，我这里就不过多解释了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000007;
int dis[maxn];
int prime[maxn];
int visit[maxn];
void Prime(){
    for (int i = 2;i <= maxn; i++) {
        if (!visit[i]) {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
int main()
{
	int n,flag=0;
	Prime();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		for(int j=1;prime[j]*prime[j]<=x;j++)
		{
			while(x%prime[j]==0)
			{
				x=x/prime[j];
				dis[i]++;
			}
		}
		if(x!=1)dis[i]++;
		flag=flag^dis[i];
	}
	if(flag==0)
	{
		printf("TT txdy!\n");
	}else
	{
		printf("CC yyds!\n");
	}
	return 0;
}

本文地址：https://blog.csdn.net/weixin_45434743/article/details/109263937