因为质因数是无法再被分解的,所以最后集合中的数全为n的质因数,先考虑把n质因数分解。不难发现,每次分解为哪2个数并不重要,只不过是把集合中的数字个数加1,那么质因数个数的奇偶很可能决定了谁最后无法操作。

假设 n 有 p 个质因数,那么这场游戏将进行 p-1 次操作(每次操作后集合中的数字个数+1),如果 p-1 为奇数那么后手便无法再进行操作,如果 p-1 为偶数则先手再无法进行操作。
注意:n==1 的情况要特殊处理一下.
(by Tang7O)

#include<cstdio>
using namespace std;
int ans;
int main() {
    int n;
    scanf("%d",&n);
    if (n==1) return printf("Nancy")&0;//特判1的情况
    for (int i=2; i<=n; i++)
        while (n%i==0) n/=i,ans++;//质因数分解
    ans&1 ? printf("Nancy"):printf("Johnson");//ans为奇数?
}