自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 21:33:54，当前版本为作者最后更新于2018-01-20 15:55:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

小K的策略：令对方不得不选择一个质数，令自己胜利。

这样小K只能选择Q的两个质因数的乘积。

由于要求可以制胜的数字最小，我们只需知道Q的两个最小质因数。

分类讨论：

1.Q是1或质数，此时小K只能选0，胜利。

2.Q是两个质数的积，小K只能选1或质数，对方选0，对方胜利。

3.Q是多个质数的积，小K有必胜策略（见上），胜利。

博弈论的部分结束了，现在我们要处理如何进行质因数分解的问题了。

对于Q，我们对于所有小于Q而大于1的正整数X，看Q能否整除X，如果可以X就是Q的因数。

如果我们在Q整除X时，Q=Q/X，再次判断Q能否整除X，这样就可以达到转化问题的效果，并且可以保证，对于每次分解出来的X，必然有X是质数，因为如果X不是质数，其必然有质因数，而这因数必然在之前已经分解掉了，所以分解出来的一定是X。

然而这样仍然会超时，我们需要考虑如何加快时间，减小时间复杂度。我们肯发现对于所有的X<=sqrt(Q)，即X*X<=Q，如果没有X能整除Q，必然有Q是质数，通过这一点，我们就可以把以上的“对于所有小于Q而大于1的正整数X”改为“对于所有小于根号Q而大于1的正整数x”，达到优化时间复杂度的目的。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;//注意一定要long long类型
ll n,ans;
queue<ll>q;//用队列来存储Q的质因数，方便加入元素，访问大小和前面（最小）元素
int main()
{
    scanf("%lld",&n);
    for(ll i=2;i*i<=n;i++)while(n%i==0)q.push(i),n/=i;//分解质因数
    if(n!=1)q.push(n);//加入最大的因子
    if(q.size()==2)printf("2\n");
    else if(q.size()==1)printf("1\n0\n");
    else
    {
        printf("1\n");
        ans=q.front();
        q.pop();
        printf("%lld\n",ans*q.front());
    }//分类讨论，具体见上
    return 0;
}