AT_abc210_f

看到这题不知道为什么第一反应是 flow。

先把每个数质因数分解，然后问题就变成了让选出的集合无交。

如果此时像我一样，发现是分成两个集合，就往最小割的方向想，就到死路了。主要是最小割就要求每两个不互质的数间都要加一个限制，无法优化。

事实上，注意到每个位置只有两种选择，抽象成选 $0/1$，就应该马上联想到 2-sat。建图方式就是如果 $A_i,B_j$ 不互质，则连 $i\to j$，$A_i,A_j$ 不互质则连 $i\to j+n$，其他同理。

发现这样还是会有 $O(n^2)$ 条边，于是优化建图，对于每一个质数开若干个虚点优化。注意不能直接每个质数开一个虚点然后对应着连，因为这样会导致 $i$ 一定能走到自己。正确的优化方式应该是对前缀/后缀分别进行前缀/后缀优化建图。

然后就 2-sat 常规跑一遍 tarjan 就行了。

code：

int n,m,cur,pm[N],f[N],id[N];
int idx,top,st[N],dfn[N],low[N];
int k,c[N],g[N];
vector<int> a[M],b[M];
bool vis[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
void tarjan(int u){
	dfn[u]=low[u]=++idx;
	st[++top]=u;
	vis[u]=1;
	go(i,u){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		k++;
		do{
			int v=st[top];
			c[v]=k;
			vis[v]=0;
		}while(st[top--]!=u);
	}
}
void Yorushika(){
	scanf("%d",&n);
	rep(i,1,n){
		int x,y;scanf("%d%d",&x,&y);
		int lst=0;
		while(x>1){
			if(f[x]!=lst){
				a[i].eb(id[f[x]]);
			}
			lst=f[x],x/=f[x];
		}
		lst=0;
		while(y>1){
			if(f[y]!=lst){
				b[i].eb(id[f[y]]);
			}
			lst=f[y],y/=f[y];
		}
	}
	cur=n+n;
	rep(i,1,n){
		for(int j:a[i]){
			if(g[j]){
				add(i,g[j]);
			}
		}
		for(int j:b[i]){
			if(g[j]){
				add(i+n,g[j]);
			}
		}
		for(int j:a[i]){
			cur++;
			if(g[j]){
				add(cur,g[j]);
			}
			add(g[j]=cur,i+n);
		}
		for(int j:b[i]){
			cur++;
			if(g[j]){
				add(cur,g[j]);
			}
			add(g[j]=cur,i);
		}
	}
	mems(g,0);
	drep(i,n,1){
		for(int j:a[i]){
			if(g[j]){
				add(i,g[j]);
			}
		}
		for(int j:b[i]){
			if(g[j]){
				add(i+n,g[j]);
			}
		}
		for(int j:a[i]){
			cur++;
			if(g[j]){
				add(cur,g[j]);
			}
			add(g[j]=cur,i+n);
		}
		for(int j:b[i]){
			cur++;
			if(g[j]){
				add(cur,g[j]);
			}
			add(g[j]=cur,i);
		}
	}
	mems(vis,0);
	rep(i,1,cur){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	rep(i,1,n){
		if(c[i]==c[i+n]){
			puts("No");
			return;
		}
	}
	puts("Yes");
}
signed main(){
	int mx=2e6;
	rep(i,2,mx){
		if(!vis[i]){
			pm[++m]=i,id[i]=m;
			f[i]=i;
		}
		rep(j,1,m){
			if(pm[j]>mx/i){
				break;
			}
			vis[i*pm[j]]=1;
			f[i*pm[j]]=pm[j];
			if(i%pm[j]==0){
				break;
			}
		}
	}
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}