题解 | #Game#

sg函数暴力求解

#include<bits/stdc++.h>
using namespace std;
const int N  = 1e5+10;
int dp[N];
int sg(int x){
    if(~dp[x])return dp[x];
    unordered_set<int>q;
    for(int i=2;i<x;i++)
    {
        if(x%i==0)q.insert(sg(i)^sg(x/i));
    }  
    for(int i=0;;i++)
    if(!q.count(i))return dp[x]=i;
}
int main(){
    memset(dp,-1,sizeof dp);
    int n;
    cin>>n;
    if(sg(n))cout<<"Johnson";
    else cout<<"Nancy";
}