Loading...

洛谷P2092 数字游戏

check评论:0 条 remove_red_eye浏览量:398 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-08

这是一道超级大水题

首先如果$Q$是质数就输出$0$就好$\text{qwq}$

如果$Q$是$1$也一样

如果$Q$的质因子个数小于$4$就肯定输了$\text{qaq}$,简单证明一下

设$f(Q)$代表$Q$的因子个数$(2 \leq Q \text{且}!isprime(Q))$

所以$f(Q)=3$,而除了$Q$和$1$,他只剩下一个质因子$(\text{否则}f(Q)!=3)$

而当他选了这个质数时,另外一个人就选不了了,就赢了

所以$f(Q)$不能小于$4$

而当$4 \leq f(Q)$时,就肯定可以了

为了保证对面选完了我们就一定选不了了,所以对面能够选择的数一定是质数

那只要剩下的数是两个质数乘积就好啦$(\text{该乘积必须是Q因数})$

上代码$\text{qwq}$

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> vc;
int flag=1;
int yueshu(int x)
{
    int cnt=1;
    for(int i=2;i*i<=x;i++)
    {
        int l=x;
        while(l%i==0)
        {
            if(vc.size()<2)
            {
                vc.push_back(i);
            }
            if(vc.size()==2&&cnt>=4)
            {
                printf("1\n%lld",vc[0]*vc[1]);
                flag=0;
                return 0;
            }
            if(i*i!=x)
            {
                cnt+=2;
            }
            l/=i;
        } 
    }
    if(cnt<4)
    {
        return 0;
    }
    return 1;
}
main()
{
    int n;
    cin>>n;
    if(yueshu(n))
    {
        printf("1\n%lld",vc[0]*vc[1]);
    }
    else
    {
        if(!flag)
        {
            return 0;
        }
        if(vc.size()==0)
        {
            cout<<1<<endl<<0;
            return 0;
        }
        else
        {
            printf("2");
            return 0;
        }
    }
}

$dp$训练集合 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名