题解：CF1656H Equal LCM Subsets

· · 题解

CF1656H Equal LCM Subsets

（最近在集训，金牌爷光速讲黑题，只听懂了这道，于是写个题解纪念一下。）

（欢迎在 CQ XF 一起集训的大佬们壶关蒟蒻）

题意：从集合 A 中选出子集 S_{A}，从集合 B 中选出子集 S_{B}，要求 \operatorname{lcm}\{S_{A}\}= \operatorname{lcm}\{S_{B}\} 的任意一种方案。

思路

首先，因为 \operatorname{lcm}\{S_{A}\}= \operatorname{lcm}\{S_{B}\}。

所以容易得出如果 x\in S_{A}，那么 x\mid \operatorname{lcm}\{S_{B}\}。

我们尝试把它展开来看，很明显（注意 N,M 不是题目给定的 n,m ）：

x=\prod_{i=1}^{N}p_{i}^{a_{i}},\operatorname{lcm}\{S_{B}\}=\prod_{i=1}^{M}p_{i}^{b_{i}}

其中 p_i 为质数。

如果 x\mid \operatorname{lcm}\{S_{B}\}，那么一定存在

\max_{i=1}^{\max(N,M)}(a_i,b_i)=b_i

举个例子：x=4,\operatorname{lcm}\{S_{B}\}=6。

很明显，4 不能整除 \operatorname{lcm}\{S_{B}\}，因为 4=2^2 而 6=2^1\times3^1。

但是，由于数据巨大，我们肯定不能直接维护 \operatorname{lcm} 的值。

于是我们考虑继续把 \operatorname{lcm}\{S_{B}\} 展开，也取出其中的一个数。

这时候，维护 x 是否能加入集合 S_{A} 中已经很难了，我们换一个思路：那就是维护不在子集中的数。

对于每一个 y\in S_B，我们想知道 x 比他多了哪些原本不该有的质因数指数。

我们就可以用 x 除以他们的 \gcd，即 \frac{x}{\gcd(x,y)}。

求出来一个数之后，我们继续来看它对于集合中其他数的影响。

举个栗子：

x=6,S_B=\{4,9\}

我们想知道 a 是否能被 4,9 的最小公倍数整除，并且知道了：

\frac{6}{\gcd(4,6)}=3,\frac{6}{\gcd(9,6)}=2

很明显，3 与 2 是互质的，所以说在 S_{A} 中加入 6，并不会影响两个集合的 \operatorname{lcm}。

所以，当 \gcd_{i=1}^{m}\frac{x}{\gcd(x,b_i)}>1 \ (b_i\in S_{B}) 时，将 x\in A 加入集合 S_{A} 中不会影响最终的答案。

所以，我们把 \frac{x}{\gcd(x,b_i)} 作为线段树的叶子节点，子树信息用 \gcd 维护，就能建出一棵线段树。

而上面这个式子的答案，就是树根的值。

我们就可以给每一个点建一棵树，初筛是否合法，获得两个子集。

但是，此时的子集并不是最终答案。因为你删掉的数，会影响上面那个式子的答案。

所以，我们拿个队列记录删除的数，每一次清除删除的数对另一个集合产生的影响，再把不能留在集合的数塞进队列里，重复直到队列清空。

此时，没有被删除的数就是答案（删完了就是无解）。

最后，给份代码。（oh 对了，不开 __int128 见祖宗 awa ）

code

#include<bits/stdc++.h>
#define pii pair<int,int>
//#define int long long
//#define ll __int128
#define int __int128
#define r second
#define l first
using namespace std;

namespace io
{
    template<typename T>inline T read(){int x=0,w=0;char c=0;while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;}
    template<typename T>inline void write(T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
    template<typename T>inline void write_(T x){write(x),putchar(' ');}
    template<typename T>inline void writeln(T x){write(x),putchar('\n');}
}
using namespace io;

int t,n,m,d[2],v[2][1<<10],a[2][1<<10];
queue<pii> q; 

struct tree
{
    #define lc k<<1
    #define rc k<<1|1
    int c[1<<11],x;
    void update(int k){c[k]=__gcd(c[lc],c[rc]);}
    void build(int f,int k,int l,int r)
    {
        if(l==r){c[k]=x/__gcd(x,a[f][l]);return;}
        int mid=(l+r)>>1;
        build(f,lc,l,mid),build(f,rc,mid+1,r);
        update(k);
    }
    void clear(int x,int k,int l,int r)
    {
        if(l==r){c[k]=0;return;}
        int mid=(l+r)>>1;
        if(x<=mid) clear(x,lc,l,mid);
        else clear(x,rc,mid+1,r);
        update(k);
    }
    int ask(){return c[1];}
}tr[2][1<<10];

void clear()
{
    while(!q.empty()) q.pop();
    d[0]=d[1]=0;
//  memset(tr,0,sizeof tr);
    memset(v,0,sizeof v);
}

int ask(int f){return f==0?n:m;}

signed main()
{
    t=read<int>();
    while(t--)
    {
        n=read<int>(),m=read<int>();
        clear();
        for(int i=1;i<=n;i++) a[0][i]=read<int>();
        for(int i=1;i<=m;i++) a[1][i]=read<int>();
        for(int f=0;f<=1;f++)
            for(int i=1;i<=ask(f);i++)
            {
                tr[f][i].x=a[f][i],tr[f][i].build(f^1,1,1,ask(f^1));
                if(tr[f][i].ask()>1) q.push(make_pair(f,i)),v[f][i]=1,++d[f];
            }
        while(!q.empty())
        {
            auto x=q.front();
            q.pop();
            int l=x.l,r=x.r;
            for(int i=1;i<=ask(l^1);i++)
                if(!v[l^1][i])
                {
                    tr[l^1][i].clear(r,1,1,ask(l));
                    if(tr[l^1][i].ask()>1) q.push(make_pair(l^1,i)),v[l^1][i]=1,++d[l^1];
                }
        }
        if(n==d[0]||m==d[1]){puts("NO");continue;}
        puts("Yes");
        write_(n-d[0]),writeln(m-d[1]);
        for(int i=1;i<=n;i++)
            if(!v[0][i]) write_(a[0][i]);
        putchar('\n');
        for(int i=1;i<=m;i++)
            if(!v[1][i]) write_(a[1][i]);
        putchar('\n');
    }
    return 0;
}

完结撒花 awa。