P4752题解

· · 题解

分析+解法

这题显然不能硬乘出来，于是考虑一种记录因数再比较的做法，但是注意这里可以只用记录是质数的因子，为什么？因为题目已经给出 b\subseteq a（因为每一个出现在 b 中的数的出现次数都小于在 a 中出现的次数，也就是说 b 所有出现的都在 a 里有对应，为 b\subseteq a），于是实际上 \complement_ab 就只能是一个质数。所以如果有合数出现，不是正好约光、就是多出来，但是因为只能多出来质数所以合数就被否定了，可以忽略；下面说一下如何记录质数，首先先要判定是不是质数，就可以运用线性筛质数+二分查找来完成：

线性筛质数：运用链表，每一次枚举链表中的 i，对于每一个 i 再枚举链表中的每一个 h， i\times h 就是一个合数，把其从链表中抹去，这样能做到真正意义上的线性，因为每一个用 i 枚举出来的合数都是以 i 为最小因子的数，于是其实每一个数都会不重不漏的被枚举刚好一遍，最后扫一遍链表放到数组里去完成。

for ( int i = 0; i < 1000005; i++ ) prime[i].bef = i - 1 , prime[i].aft = i + 1;
for ( int i = 2; prime[i].bef <= 1000000; i = prime[i].aft )
{
    cnt = 0;
    for ( int h = 2; i * h <= 1000000; h = prime[h].aft )   q[++cnt] = i * h;
    for ( int h = 1; h <= cnt; h++ )    aa = prime[q[h]].bef , bb = prime[q[h]].aft , prime[aa].aft = bb , prime[bb].bef = aa;
}
for ( int i = 2; i <= 1000000; i = prime[i].aft )   p[++cmp] = i;

二分查找：因为质数数组是严格递增的，于是可以运用二分查找的性质，以 \log 级别的时间复杂度找到大于这个数的最小数对应数组内的位置，然后将这个位置代入数组找到对应数字，判断这个数字是否等于正在查找的数字，如果是那么这个数字就在数组里面，否则就不在。

int fnd( ll x[] , ll y )
{
    if ( x[upper_bound( x , x + 202515 , y ) - x - 1] == y )    return 1;
    return 0;
}

下面我们就进入最后一个板块：判断是否只多出来一个质数。如何做？我们本应该很简单的运用桶排，但是无奈数据规模过于庞大，我们运用优先队列，找到质数都push到队列里去，最后扫一遍两个队列，如果出现了不一样的，也就是 a 中比 b 多出了一个质数，标记并单独踢掉它，如果下次又遇到了就直接结束程序，输出 NO 。如果到最后有且仅有一次遇到不同的，就可以，否则就不可以。

下面是代码实现：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p[202515] , cmp , q[1000005] , cnt , aa , bb , t;
int fnd( ll x[] , ll y )
{
    if ( x[upper_bound( x , x + 202515 , y ) - x - 1] == y )    return 1;
    return 0;
}
priority_queue<int> p1 , p2;
struct P
{
    int bef , aft;
    bool flag = true;
}prime[1000005];
ll m , n , a[100005] , b[100005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL) , cout.tie(NULL);
    for ( int i = 0; i < 1000005; i++ ) prime[i].bef = i - 1 , prime[i].aft = i + 1;
    for ( int i = 2; prime[i].bef <= 1000000; i = prime[i].aft )
    {
        cnt = 0;
        for ( int h = 2; i * h <= 1000000; h = prime[h].aft )   q[++cnt] = i * h;
        for ( int h = 1; h <= cnt; h++ )    aa = prime[q[h]].bef , bb = prime[q[h]].aft , prime[aa].aft = bb , prime[bb].bef = aa;
    }
    for ( int i = 2; i <= 1000000; i = prime[i].aft )   p[++cmp] = i;
    cin >> t;
    while ( t-- )
    {
        cin >> n >> m;
        for ( int i = 1; i <= n; i++ )
        {
            cin >> a[i];
            if ( fnd( p , a[i] ) )  p1.push( a[i] );
        }
        for ( int i = 1; i <= m; i++ )
        {
            cin >> b[i];
            if ( fnd( p , b[i] ) )  p2.push( b[i] );
        }
        bool flag = false , jug = true;
        if ( p1.size() <= p2.size() )   cout << "NO\n";
        else
        {
            while ( !p2.empty() )
            {
                if ( p1.top() != p2.top() && !flag )    flag = true , p1.pop();
                else    if ( p1.top() != p2.top() && flag )
                {
                    cout << "NO\n" , flag = false , jug = false;
                    break;
                }
                else    p1.pop() , p2.pop();
            }
            if ( flag || p1.size() == 1 && p2.size() == 0 ) cout << "YES\n";
            else    if ( jug )  cout << "NO\n";
        }
        while ( !p1.empty() )   p1.pop();
        while ( !p2.empty() )   p2.pop();
    }
    return 0;
}