魔法珠

sg函数ε唉,令人自闭的东西.
考虑有向图建边(sg函数mex定义只是针对0?...不是很懂ε唉)
对于每个局面单独考虑,计算出它能转移的状态,然后根据sg^和为0判定游戏胜负.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N];
int f[N];

int yue_mo(int *yue,int n)
{
    int cnt=0;
    for(int i=1;i<n;i++)
    {
        if(n%i==0)  yue[++cnt]=i;
    }
    return cnt;
}

int solve(int x)
{
    if(f[x]!=-1)    return f[x];
    int yue[x];
    bool hash[N];
    memset(hash,false,sizeof hash);
    int len=yue_mo(yue,x),k=0;
    for(int i=1;i<=len;i++)
    {
        k^=solve(yue[i]);
    }
    for(int i=1;i<=len;i++)
    hash[solve(yue[i])^k]=1;
    for(int i=0;;i++)
    {
        if(!hash[i])
        {
            f[x]=i;
            break;
        }
    }
    return f[x];
}

int main()
{
    int n;
    while(cin>>n)
    {
        int ans=0;
        memset(f,-1,sizeof f);
        f[1]=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            ans^=solve(a[i]);
        }
        if(ans)    puts("freda");
        else       puts("rainbow");
    }
    return 0;
}