题解：CF1656H Equal LCM Subsets

· · 题解

题面

美妙多校讨论，带来新科技。

我们考虑如果我们已经把所有的 a_i,b_i 都分解成了 \prod\limits_{i=1}^kp_i^{x_i},\prod\limits_{i=1}^kp_i^{y_i} 的形式，那我们就可以考虑对于每一个质数建两个大根堆维护 a,b 两个数列中的数以这个质数为底数的最大指数。每次扫一遍所有的质数，如果发现 maxa_i\not=maxb_i，就将大的那个数删掉再继续扫；如果发现所有有一边被删完了或者没有不同的位置就表明找到了答案，复杂度 O(n^2d(V)\log n)。

然后我们发现好像分解质因数是唯一的瓶颈。

现在我们考虑用其他题解说的线段树再仔细想想。

我们发现我们要的并不是把 a_i,b_i 分解为质数，而是要找一个数组 c_{\{k\}} 满足 \forall 1\le i<j\le k,\gcd(c_i,c_j)=1 且每个 a_i,b_i 都可以表示为 \prod\limits_{i=1}^kc_i^{x_i}。

结合 CF 大神的文章，我有一个可以大概在 O(n^2\log ^2 V) 的复杂度找到一个长度为 n\log V 的数组 c。（没看懂单 \log 的操作）

我们考虑已经求出了一个前缀对应的 c，现在考虑加入一个 x，如果 x 与 c 中所有数都互质就将其加入 c；如果存在一个 \gcd(c_i,x)=d,d>1，将 c_i 替换为 \dfrac{c_i}d，并再次尝试将 d,\dfrac xd 加入。（记得把 c 里所有的 1 删掉）

尝试证明复杂度（有错请指出）：

首先，我们知道，这玩意最后找出来的数组长度不可能比所有 a_i,b_i 的不同质因数还多，所以总长度最多是 n\log V 级别（好像是 \log\log，但是不重要吧？）。

另外，我们记所有的数的总乘积为 P(包括未加入的数和 c 中的数)，我们发现，每次找到一个与 x 不互质的 c_i，会将 c_i,x 变为 \dfrac{c_i}d,\dfrac xd,d，也就是将 P 变为 \dfrac Pd，所以这种操作最多是进行 \log(V^n)=n\log V 次，而每次都是遍历整个 c 数组，即遍历 n\log V 个元素，总复杂度就是 O(n^2\log ^2 V)。

其实感觉这个远远跑不满，如果有更严格的上界欢迎来写题解。

总复杂度 O(n^2\log ^2V)。

洛谷已有记录里第 3 优解。

代码：

#include<bits/stdc++.h>
#define int __int128
using namespace std;
char buf[1000005],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=0,c=gc();
    while(!isdigit(c))f|=(c=='-'),c=gc();
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=gc();
    return f?-x:x;
}
char puf[1000005];
int ptot;
#define pc(x) putchar(x)
int num[45],ntot;
inline void print(int x){
    if(x<0){
        pc('-');
        print(-x);
        return;
    }
    ntot=0;
    do{
        num[ntot++]=x%10;
        x/=10;
    }while(x);
    for(int i=ntot-1;i>=0;i--)pc(num[i]+48);
}
int T,n,m,tot,a[1005],b[1005],c[250005];
bool visa[1005],visb[1005];
void Insert(int x){//插数
    for(int i=1;i<=tot;i++){
        if(__gcd(x,c[i])!=1){//找到了
            int d=__gcd(x,c[i]);
            c[i]/=d;
            x/=d;
            if(d>1)Insert(d);
            if(x>1)Insert(x);
            return;
        }
    }
    c[++tot]=x;//没找到
}
struct node{
    int x,y;
    bool operator<(const node &t)const{return x<t.x||(x==t.x&&y<t.y);}
    bool operator>(const node &t)const{return x>t.x||(x==t.x&&y>t.y);}
    bool operator==(const node &t)const{return x==t.x&&y==t.y;}
};
vector<node>x[1005],y[1005];
struct Heap{//堆维护
    priority_queue<node>qa,ra;
    void Push(node x){
        qa.push(x);
    }
    void Erase(node x){
        ra.push(x);
    }
    node Max(){
        while(!qa.empty()&&!ra.empty()&&qa.top()==ra.top())qa.pop(),ra.pop();
        if(qa.empty())return node({-1,-1});
        return qa.top();
    }
    bool empty(){
        return !(qa.size()-ra.size());
    }
    void clear(){
        while(!qa.empty())qa.pop();
        while(!ra.empty())ra.pop();
    }
}qa[250005],qb[250005];
signed main()
{
    T=read();
    while(T--){
        n=read(),m=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=m;i++)b[i]=read();
        tot=0;
        for(int i=1;i<=n;i++)Insert(a[i]),visa[i]=1;
        for(int i=1;i<=m;i++)Insert(b[i]),visb[i]=1;
        int Tt=0;
        for(int i=1;i<=tot;i++)if(c[i]!=1)c[++Tt]=c[i];
        tot=Tt;
        for(int i=1;i<=tot;i++)qa[i].clear(),qb[i].clear();
        for(int i=1;i<=n;i++){
            x[i].clear();
            int A=a[i];
            for(int j=1;j<=tot;j++){
                if(a[i]%c[j]==0){
                    int tmp=0;
                    while(a[i]%c[j]==0){
                        a[i]/=c[j];
                        tmp++;
                    }
                    x[i].push_back(node({j,tmp}));
                    qa[j].Push(node({tmp,i}));
                }
            }
            a[i]=A;
        }
        for(int i=1;i<=m;i++){
            y[i].clear();
            int A=b[i];
            for(int j=1;j<=tot;j++){
                if(b[i]%c[j]==0){
                    int tmp=0;
                    while(b[i]%c[j]==0){
                        b[i]/=c[j];
                        tmp++;
                    }
                    y[i].push_back(node({j,tmp}));
                    qb[j].Push(node({tmp,i}));
                }
            }
            b[i]=A;
        }
        bool f=0;
        int X=n,Y=m;
        while(X&&Y){
            bool fff=1;
            for(int i=1;i<=tot;i++){
                if(qa[i].Max().x!=qb[i].Max().x){
                    fff=0;
                    if(qa[i].Max().x>qb[i].Max().x){
                        node tmp=qa[i].Max();
                        int id=tmp.y;
                        for(auto op:x[id]){
                            qa[op.x].Erase(node({op.y,id}));
                        }
                        visa[id]=0;
                        X--;
                    }
                    else{
                        node tmp=qb[i].Max();
                        int id=tmp.y;
                        for(auto op:y[id]){
                            qb[op.x].Erase(node({op.y,id}));
                        }
                        visb[id]=0;
                        Y--;
                    }
                }
            }
            if(fff){
                f=1;
                pc('Y'),pc('E'),pc('S'),pc(10);
                print(X),pc(' '),print(Y),pc(10);
                for(int i=1;i<=n;i++){
                    if(visa[i]){
                        print(a[i]);pc(' ');
                    }
                }
                pc(10);
                for(int i=1;i<=m;i++){
                    if(visb[i]){
                        print(b[i]);pc(' ');
                    }
                }
                pc(10);
                break;
            }
        }
        if(!f)pc('N'),pc('O'),pc(10);
    }
    return 0;
}