自动搬运

查看原文

来自洛谷，原作者为

	csb0118 唯有爱与洛谷，不可辜负

搬运于2025-08-24 22:58:40，当前版本为作者最后更新于2024-07-29 13:07:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10506 魔法珠 题解

这道题很容易可以想到把每一个输入的 $ai$ 作为一个有向图游戏的起点，只要求出这 $n$ 个有向图游戏的和就可以得出结论。

具体实现

对于其中的每一个数 $m$，设它存在 $x$ 个小于 $m$ 的因数，那么 $m$ 就一定存在 $x$ 个子状态。 我们把每一个合法产生的子状态所构成的集合做 mex 运算，就可以求出 $m$ 的 SG 值。

最后我们把所有数的 SG 值作异或运算，得到有向图游戏的和，就可以判断是先手必胜还是后手必胜。

代码：

#include<bits/stdc++.h>
using namespace std;
int sg[1001],a[1001];
int SG(int m){
    if(sg[m]!=-1)
		return sg[m];
    int k=0;
    for(int i=1;i*i<=m;++i)
        if(m%i==0){
	        if(i<m)
				k^=SG(i);
	        if(m/i>1&&m/i<m&&i*i!=m)
				k^=SG(m/i);
 	   }
 	bool flag[1001];
    memset(flag,0,sizeof flag);
    for(int i=1;i*i<=m;++i)
        if(m%i==0){
	      	if(i<m)
			  	flag[k^sg[i]]=1;
	        if(m/i>1&&m/i<m&&i*i!=m)
				flag[k^sg[(m/i)]]=1;
    	}
    int t=0;
    while(flag[t])
		t++;
    return sg[m]=t;
}
void work(int n){
	memset(sg,-1,sizeof(sg));
    sg[1]=0;
	int ans=0;
    for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ans^=SG(a[i]);
	}
    if(ans!=0)
    	cout<<"freda"<<endl;
    else
    	cout<<"rainbow"<<endl;
    return ;
}
int main(){
    int n;
    while(cin>>n)
    	work(n);
	return 0;
}