题解 P4752 【Divided Prime】

这是一个不需要$STL$的方法
因为每个因子都很大,所以我们不可能直接乘起来再除(这不是废话),而题目保证对于一个数字,其在$b_i$中出现的次数不多于在$a_i$中出现的次数,所以我们很容易想到要把$a$中的数用$b$里的约分掉,而众所周知,$a\land a=0$,于是我们就可以考虑利用异或来约分,主要细节看代码说吧。

#include<cstdio>
using namespace std;
typedef long long ll;
ll re()//快读
{
    ll x=0;
    char c=getchar();
    bool p=0;
    for(;c<'0'||c>'9';c=getchar())
        p=(c=='-'||p)?1:0;
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+(c-'0');
    return p?-x:x;
}
bool judge(ll x)//判断是否是质数
{
    int i;
    if(!x||x==1)//特判0和1
        return false;
    for(i=2;1LL*i*i<=x;i++)//朴素根号n试除法判断
        if(!(x%i))
            return false;
    return true;
}
int main()
{
    int i,n,m,t,s;
    ll x,y;
    t=re();
    while(t--)//多组数据
    {
        x=y=s=0;//初始化为0
        n=re();
        m=re();
        for(i=1;i<=n+m;i++)//因为异或的性质,我们可以一次性读完并异或
        {
            y=re();
            if(y!=1)//注意!因为无论有多少个1,都是不影响结果的,所以在异或时要把1排除
            {
                i>n?s--:s++;//显然(除去1后)只有当a里的数比b里的数多一个时才可能是质数,所以我们通过统计来判断
                x^=y;//将所有数异或起来,如果满足上述“多一个”的条件,则异或完所剩下的必是没有被约分的数
            }
        }
        if(s==1&&judge(x))//判断是否满足上述“多一个”的条件,且这个剩余的数是否质数
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

另外,我用下面这个数据,将一个题解卡掉了

1
5 2
1 1 1 2 3
1 2

正确输出:YES

发表于 2018-07-16 20:07:54 in 题解