题解 P1621 【集合】

解题报告：

筛出1-100000当中所有的素数 进行预处理

采用线性筛 不会请左转 P3383 【模板】线性筛素数

对于集合划分 很自然就会想到用并查集维护其连通性 对于性质相同的元素合并入同一个集合 最后统计父亲节点个数即可

刚开始有一个地方想错了

我刚开始是这样进行并查集维护的

	px=find(prime[i]);
	for (int j=1;j*prime[i]<=b;j++){
		py=find(j*prime[i]);
		if (px==py) continue;
		f[py]=px;
     	}

然后统计在a-b区间内的祖先节点个数 乍一看很对 其实错得很离谱

仔细想一想就会知道 这样维护的话 最后的祖先节点会统一到

$prime[i]$ 上去 如果出现一个$prime[i]$不在a-b的区间内 就会

有一部分的父亲节点在区间外 那么统计答案答案时候就会丢失一部分数据

那么怎么办呢？

找出当前素数在a-b的范围表示的第一个数 然后在进行维护的时候 统一到第一个数 那么我们最后在进行扫描的时候 就可以保证对于每一个集合的父亲都在区间内

代码如下：

#include<bits/stdc++.h>
using namespace std;
int prime[100005],v[100005],tot;
int a,b,p,f[100005],px,py,ans;
void pri(){
	for (int i=2;i<=100000;i++){
		if (!v[i]){
			v[i]=i;
			prime[++tot]=i; 
		}
		for (int j=1;j<=tot;j++){
			if (v[i]<prime[j]||i*prime[j]>100000) break;
			v[prime[j]*i]=prime[j];
		}
	}
}
int find(int x){
	if (x==f[x]) return x;
	return f[x]=find(f[x]);
}
int main(){
	pri();
	//for (int i=1;i<=100;i++) printf("%d
",prime[i]);
	scanf("%d%d%d",&a,&b,&p);
	for (int i=1;i<=100005;i++) f[i]=i; 
	for (int i=1;i<=tot;i++)
		if (prime[i]>=p){
		/*
			px=find(prime[i]);
			for (int j=1;j*prime[i]<=b;j++){
				py=find(j*prime[i]);
				if (px==py) continue;
				f[py]=px;
		*/
		//集合合并错误 不是与素数合并为一个集合 而是与在a-b的范围类符合条件的数合并为一个集合
			int flag=1,tmp; 
			for (int j=1;j*prime[i]<=b;j++){
					if (j*prime[i]>=a&&flag){
						tmp=j*prime[i];
						flag=0;
						px=find(tmp);
					}//寻找第一个符合条件的数 作为集合合并的对象
					if (j*prime[i]>=a){
						py=find(j*prime[i]);
						if (px==py) continue;
						f[py]=px;
					}		
				}
			} 
	for (int i=a;i<=b;i++)
		if (f[i]==i) ans++;
	printf("%d
",ans);
	return 0;
}