题解：P11867 大家的公因数 2

· · 题解

没打比赛，赛后独立做出来的。

首先可以搞个桶上去。

然后跑线性筛，把每个质数视作一个点进行连边。

这样就建了图。

糊个并查集上去判掉不连通的情况。剩余问题离线出来，按照连通块排序。

容易发现一个限制能做当且仅当所在连通块能异或出指定数。

所以对于每个连通块的问题可以搞个线性基处理。

做完了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MB=60;
int a[500005],flc[10000005],fa[10000005],p[MB+5],d[MB+5],top,N;
bool aa[10000005],ans[500005],vis[10000005];
vector<int>ve[10000005];
struct fish{
    int u,v,z;
    int id;
    int fa;
}Q[500005];
void ins(int x){
    if(!x)return;
    for(int i=MB;i>=0;i--)
    if((1ll<<i)&x){
        if(!p[i]){p[i]=x;break;}
        else x^=p[i];
    }
}
bool ask(int x){
    for(int i=MB;i>=0;i--)
    if((1ll<<i)&x)x^=p[i];
    return x==0;
}
int find(int x){
    return(x==fa[x]?x:fa[x]=find(fa[x]));
}
void zss(int n){
    for(int i=2;i<=n;i++)
    if(!aa[i]){
        for(int j=1;j*i<=n;j++){
            aa[j*i]=true;
            if(flc[j*i]!=-1)
            fa[find(j*i)]=find(i);
        }
    }
}
bool cmp(fish x,fish y){
    return x.fa<y.fa;
}
void news(int x){
    memset(p,0,sizeof p);
    memset(d,0,sizeof d);
    for(int i=0;i<ve[x].size();i++)ins(flc[ve[x][i]]);
}
signed main(){
    int n,q;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],N=max(N,a[i]);
    for(int i=1;i<=N;i++)fa[i]=i,flc[i]=-1;
    for(int i=1,x;i<=n;i++)cin>>x,flc[a[i]]=x;
    zss(N);
    cin>>q;
    for(int i=1;i<=q;i++){
        int u,v,z;
        cin>>u>>v>>z;
        if(find(u)!=find(v))continue;
        Q[++top].u=u,Q[top].v=v,Q[top].z=z,Q[top].id=i,Q[top].fa=find(u);
        vis[find(u)]=1;
    }
    sort(Q+1,Q+1+top,cmp);
    for(int i=1;i<=N;i++)
    if(vis[find(i)])ve[find(i)].push_back(i);
    for(int i=1;i<=top;i++){
        if(Q[i].fa!=Q[i-1].fa)news(Q[i].fa);
        if(ask(Q[i].z))ans[Q[i].id]=1;
    }
    for(int i=1;i<=q;i++)puts((ans[i]?"Yes":"No"));
    return 0;
}

本来写了 123 行，太难读了，于是现在只有 71 行。

效率比较低劣，跑了 40s 以上。

注意建图和并查集的一些细节。

提交记录。

建议评蓝或紫。