牛客小白月赛21 G题——Game

每次操作可以将集合中的一个数字分解为它的任意两个非1的因数, 集合中的数字个数+1。
因为 质因数 是无法再被分解的,所以最后集合中的数全为 n 的质因数。因此只需要看题目给定的 n 有多少个质因数。假设 n 有 p 个质因数，那么这场游戏将进行 p-1 次操作（每次操作后集合中的数字个数+1），如果 p-1 为奇数那么后手便无法再进行操作，如果 p-1 为偶数则先手再无法进行操作。

注意：n==1 的情况要特殊处理一下.

AC代码如下：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define PI acos(-1)
#define debug(a) cout << (a) << endl
typedef long long ll;
int dir8[8][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
int dir4[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };
const int INF = 0x3f3f3f3fLL;
const long long LLF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXn = 95718 + 15;
const int mod = 20010905;

int s[MAXn];
int main()
{
    int n;
    int cnt=0;
    cin>>n;
    if(n==1){ //特殊处理 n==1
        printf("Nancy\n");
        return 0;
    }
    for(int i=2;i<=n;i++){ //求质因数个数
        while(n%i==0)
        {
            n/=i;
            cnt++;
        }
    }
    if(cnt%2==0) //判奇偶
        printf("Johnson\n");
    else printf("Nancy\n");
    return 0;
}