TYVJ 2049 마법구슬 sg 함수

제목: 링크

방법:sg 함수

확인:

tyvj 문제는 대부분 안 풀렸네요. - 그런데 이게 더 나을 것 같은데?이 문제를 푸려면 스스로 머리를 써야 될 것 같아요. - 입으로는 짜증나지만 마음속으로는 호평?

본론으로 돌아가다

sg[x]를 설정하여 x의 sg값을 표시하는 것은 쓸데없는 말인 것 같다

그리고 읽은 a[i]에 대해 모든 a[i]의 sg값을 다르게 하거나 0이 아니면 먼저 이기고 반대로 한다.

지킬 때 구덩이가 있어요.

약속수를 구할 때마다 수조는 sg에서 열려야 한다. 왜냐하면 귀속되면 전체 변수가 바뀌고 갱사되기 때문이다.

그리고 어떻게 유지를 했냐면요.

x에 대해 먼저 약수를 구하다

그 다음에 어떤 수를 일일이 열거하지 않고 다른 이혹은

그다음에 AC가 됐어요.

코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 110
using namespace std;
int n,cnt;
int num[N];
int sg[1010];
int b[1100];
void get(int x)
{
    cnt=1,b[cnt]=1;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            if(i*i==x)b[++cnt]=i;
            else b[++cnt]=i,b[++cnt]=x/i;
        }
    }
}
int ssgg(int x)
{
    if(sg[x]!=-1)return sg[x];
    int v[1010];memset(v,0,sizeof(v));
    get(x);
    int tot=cnt,cal[110];
    for(int i=1;i<=cnt;i++)cal[i]=b[i];
    for(int i=1;i<=tot;i++)
    {
        int ans=0;
        for(int j=1;j<=tot;j++)
        {
            if(i==j)continue;
            ans^=ssgg(cal[j]);
        }
        v[ans]=1;
    }
    for(int i=0;;i++)if(!v[i])return sg[x]=i;
}
int main()
{

    while(~scanf("%d",&n))
    {
        memset(sg,-1,sizeof(sg));sg[1]=0;
        for(int i=1;i<=n;i++)scanf("%d",&num[i]);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans^=ssgg(num[i]);
        }
        if(ans)printf("freda
");
        else printf("rainbow
");
    }
}