题解：P10506 魔法珠

· · 题解

P10506 魔法珠 题解

这道题很容易可以想到把每一个输入的

ai

作为一个有向图游戏的起点，只要求出这

n

个有向图游戏的和就可以得出结论。

具体实现

对于其中的每一个数

$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;
}