今天比较能干状态好，一天两更

老规矩，题目链接：https://codeforces.com/problemset/problem/1553/G。

题目大意如下：n个节点，每个节点存有互不相同的数字，为了方便我们称这个数字为value，当value_i和value_j不互质时，节点i和j就有一条边直接相连。然后你可以进行一种操作：对于任意i，生成一个点，这个点的value为value_i*(value_i+1)，并且也会与不互质的点相连。现给出u点和v点，去求最少经过多少次上述操作，使得u点和v点直接或间接相连。

这种只考虑连通性的问题，马上可以想到的数据结构：并查集。而且通过观察我们能发现，上述操作最多最多需要两次，如下是验证：

• 如果u和v已经在同一集合中了，那就不用连边了。（如果u和v都是偶数，那这两个数字肯定在同一集合了，因为都有约数2）
• 如果u和v一个奇数一个偶数，那么可以让二者之奇数点，生成一个新的点，生成点value必定是偶数，并且都会与u，v直接相连
• 如果二者都是奇数，那么就让u和v都去生成点，2次操作

当然，以上只是在证明为什么最多两次操作就能联通，而非最终解法，注意最多二字，也就是说用以上做法去写代码是能被找出反例的。

下面是思路以及正解：

对于每个数字都先求出质因数集：代码如下：

cin>>n>>q;
vector<int>a(n+1);
for(int i=1;i<=n;i++) {cin>>a[i];}
int maxn=*max_element(a.begin(),a.end());
vector<vector<int> >divisor(maxn+2);
for(int i=2;i<=maxn+1;i++){
	if(divisor[i].size()) continue;
	for(int j=i;j<=maxn+1;j+=i) divisor[j].push_back(i);
}

然后依据质因数集进行并查集合并操作：

for(int i=1;i<=n;i++){
	int x=a[i];
	for(int j=0;j<divisor[x].size();j++){
		merge(x,divisor[x][j]);
	}
}

以下是本题精髓，新造出来的数字是value_i*(value_i+1),这多制造出来的其实是这个(value_i+1)，它的出现使得有些集合会被连起来，具体哪些集合会被连起来呢是它所有的质因数集所在集合以及value_i两两相连。知道这个了，那可以对所有的value_i做一个预处理，计算出value_i*(value_i+1)被制造出之后会使得哪些集合会被连接起来，将所有可以通过一次操作就能连接的集合对保存下来，具体参考下面的代码

map<pair<int,int>,bool>m;
for(int i=1;i<=n;i++){
	vector<int> node=divisor[a[i]+1];
	node.push_back(a[i]);
	for(int j=0;j<node.size();j++){
		for(int k=j+1;k<node.size();k++){
			int fir=find(node[j]),sec=find(node[k]);
			m[{fir,sec}]=1,m[{sec,fir}]=1;
		}
	}
}

剩下最后的就是一个简单输出操作了

while(q--){
	int u,v;
	cin>>u>>v;
	u=a[u],v=a[v];
	if(find(u)==find(v)){
		puts("0");
	}
	else
	if(m[{find(u),find(v)}])
	puts("1");
	else puts("2");
}

最后是整体代码，且做且珍惜！

#include <bits/stdc++.h>
using namespace std;
int n,q,fa[1000500];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	if(find(x)==find(y)) return;
	fa[find(x)]=find(y);
}
int main(){
	cin>>n>>q;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++) {cin>>a[i];}
	int maxn=*max_element(a.begin(),a.end());
	for(int i=1;i<=maxn;i++) fa[i]=i;
	vector<vector<int> >divisor(maxn+2);
	for(int i=2;i<=maxn+1;i++){
		if(divisor[i].size()) continue;
		for(int j=i;j<=maxn+1;j+=i) divisor[j].push_back(i);
	}
	for(int i=1;i<=n;i++){
		int x=a[i];
		for(int j=0;j<divisor[x].size();j++){
			merge(x,divisor[x][j]);
		}
	}
	map<pair<int,int>,bool>m;
	for(int i=1;i<=n;i++){
		vector<int> node=divisor[a[i]+1];
		node.push_back(a[i]);
		for(int j=0;j<node.size();j++){
			for(int k=j+1;k<node.size();k++){
				int fir=find(node[j]),sec=find(node[k]);
				m[{fir,sec}]=1,m[{sec,fir}]=1;
			}
		}
	}
	while(q--){
		int u,v;
		cin>>u>>v;
		u=a[u],v=a[v];
		if(find(u)==find(v)){
			puts("0");
		}
		else
		if(m[{find(u),find(v)}])
		puts("1");
		else puts("2");
	}
	return 0;
}