Game
Game
http://www.nowcoder.com/questionTerminal/17b0857c1b4c497fb92875e58753a10f
题目描述
Nancy喜欢博弈！
Johnson和Nancy得到了一个神奇的多重集合，仅包含一个正整数n，两个人轮流进行操作。
一次操作可以将集合中一个数字分解为它的任意两个非1的因数，并加入集合中。
他们想知道，在Johnson和Nancy绝顶聪明的情况下，如果Nancy先手进行操作，最后谁没有办法继续操作了呢？
输入描述:
第一行：一个整数n。
数据满足：1<=n<=95718
输出描述:
共一行：一个字符串，表示最后谁（Johnson或者Nancy）无法进行操作。
思路：
这道题考察算数基本定理，算数基本定理的概念如下：
算数基本定理：
任何一个大于1的自然数 N ，如果 N不为质数，都可以 唯一分解成有限个质数；
这个定理的证明比较繁琐，而且对于我们做题没什么实际的研讨价值，有兴趣的同学可以在百度百科自行了解一下。
这个定理为我们提供了一些非常有用的性质。
首先，都可以 说明每个数字都是由若干个素数组成的。其次， 唯一 说明只要有一个Pi或者ai不同，那么一定对应了两个不同的 N。
所以，对这个数N分解质因数就可以了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[100000], cnt[100000];
int main()
{
int ans = 0, res = 1;
memset(pri, 1, sizeof(pri));
for (int i = 2;i <= 95720;i++)
if (pri[i])
for (int j = i + i;j <= 95729;j+=i)
pri[j] = 0;
for (int i = 2;i <= 95720;i++)
if (pri[i])
cnt[res++] = i;
/*for (int i = 1;i < 100;i++)
cout << cnt[i] << " ";*/
int n;
cin >> n;
if (pri[n])
{
cout << "Nancy" << endl;
return 0;
}
int i = 1;
while (n > 3 && i < res)
{
if (n % cnt[i] == 0)
{
ans++;
n /= cnt[i];
if(pri[n])
break;
}
else
{
i++;
}
}
if (ans % 2 == 1)
cout << "Johnson" << endl;
else
cout << "Nancy" << endl;
return 0;
} 求牛币，qwq。
投递快手等公司10个岗位 >