Game 题解
Game
https://ac.nowcoder.com/acm/contest/5634/C
只需要算出n可以分解多少次即可。
就比如说12可以分一次分为3 4,4又可以分为2 2.
当次数为偶数时输出Nancy
奇数为Johnson
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;
}
} 