Game 题解

import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
    public static HashMap<Integer,Long>map = new HashMap<>();
    public static void main(String args[])throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        long sum=0;
            sum+=xpp(n);
        if(sum%2==1)
            out.println("Johnson");
        else{
            out.println("Nancy");
        }
        out.flush();
    }
    public static long xpp(int x)
    {
        long sum=0,max=0;
        if(!map.containsKey(x))
        {
            for(int i=2;i*i<=x;i++)
        {
                sum=0;
                if(x%i==0)
                {
            if(check(i)==true)
            {
                sum+=xpp(i);
            }
            if(check(x/i)==true)
            {
                sum+=xpp(x/i);
            }
                sum++;
                }
                max = Math.max(max,sum);
        }
            map.put(x,max);
        return max;
        }
        else
            return map.get(x);
    }
    public static boolean check(int x)
    {
        for(int i=2;i*i<=x;i++)
        {
            if(x%i==0)
                return true;
        }
        return false;
    }
}