「LuoguP4752」牧 Divided Prime（判质数

Description

给定一个数字 A，这个 A 由 a1,a2,⋯,aN相乘得到。
给定一个数字 B，这个 B 由 b1,b2,⋯,bM相乘得到。

如果 A/B 是一个质数，请输出YES，否则输出NO。

Input

每个测试点包含多组数据，第一行读入一个整数 TTT 表示数据组数，对于每组数据：

第一行输入两个整数 N,M ，分别表示 A 由 N 个数字相乘得到， B 由 M 个数字相乘得到。

第二行输入 N 个整数，分别表示组成 A 的 N 个数字。

第三行输入 M 个整数，分别表示组成 B 的 M 个数字。

保证对于一个数字，其在 bi 中出现的次数不多于在 ai 中出现的次数。

Output

对于每组数据：

如果 A/B 是一个质数，请输出YES，否则输出NO。

在输出YES或NO后输出一个换行符。

Sample Input

2
3 2
5 7 7
5 7
4 2
5 7 7 7
5 7

Sample Output

YES
NO

Hint

1≤M≤N≤1000001

1≤ai,bi≤10121

1≤T≤10

∑N≤100000

题解

划重点：

保证对于一个数字，其在 bi 中出现的次数不多于在 ai 中出现的次数。

也就是说在把相同的构成数约掉之后，分母会约到一

于是此题约掉相同因子后转化为

给 n - m 个正整数 ai ( 1 < = i < = n - m , 1 < = ai < = 1 e 12 ) 求这些数乘起来是否为质数

~~然后xjb乱搞不是随随便便！！！(完结撒花~~

设k=n-m，遍历a数组，如果一个数既满足是约剩下的，又值为1的话，k–（表示有用的数又少了一个！~~(撒花~~）

最后如果k==1，表示恰好剩下了一个有用的数，那么判断这个有用的数是否为质数是输出yes否输出no

否则如果k==0 也就是说分子和分母一样也就是说A/B==1 且1不是质数所以输出no

而k>=2时，显然分子由k个非零且非一的数乘起来，~~那还质数个毛线啊质，~~输出no

/考场代码思路不清晰凑合看

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

#define R register

long long a[100007];

long long b[100007];

/*

inline long long read()

{

    char ch=getchar();

    long long x=0;bool s=1;

    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}

    return s?x:-x;

}

*/

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        for(R int i=1;i<=n;++i)

        scanf("%lld",&a[i]);

        sort(a+1,a+n+1);

        for(R int i=1;i<=m;++i)

        scanf("%lld",&b[i]);

        sort(b+1,b+m+1);

        if(n-m==0){cout<<"NO"<<endl;}

        else

        {

            int i=1,j=1;

            while(a[i]==1)++i;

            while(b[j]==1)++j;

            int k=n-m-i+j;

            if(k!=1){cout<<"NO"<<endl;}

            //else if(k==0){cout<<"YES"<<endl;}

            else

            {

                while(a[i]==b[j])++i,++j;

                long long x=a[i],flag=0;

                //cout<<x<<endl;

                for(long long i=2;i<=sqrt(x)&&!flag;++i)

                if(x%i==0)flag++;

                if(!flag)

                cout<<"YES"<<endl;

                else cout<<"NO"<<endl;

            }

        }

    }

    return 0;

}

巴特西