洛谷P1621 集合（c嘎嘎）

题目链接：P1621 集合 - 洛谷 | 计算机科学教育新生态

题目难度：普及/提高

解题思路:这个题要求我们在一个区间[A,B]中找出几个集合,集合中的数满足是一个大于等于P的质因数的个数,我们想到了并查集来维护这个集合，初始时候每个数的父亲就是本身，我们明确了求解答案的条件，就是将所有有大于等于P的质因数的一堆数合并起来，统计父亲是自己的个数，我们可以用筛法来求，将所有公共质因数的数在筛法过程中直接合并。最后输出答案即可。

下面奉上代码部分：

#include<bits/stdc++.h>
using namespace std;	
#define _for(i,a,b) for(int i=(a); i<(b); i++)
#define _rep(i,a,b) for(int i=(a); i<=(b); i++)
typedef long long ll;
const int N = 1e5 + 10;
bool prime[N];
int f[N];
int a,b,p;

int find(int x)
{
	if(f[x] != x) f[x] = find(f[x]);
	return f[x];
} 

int get_prime()//埃氏筛
{
	int ans = b - a + 1;//将答案初始化为a~b间数的个数，每合并一次减1就可以了
	for(int i=2; i<=b; i++)
	{
		if(!prime[i])
		{
		  if(i >= p)
		  {
			for(int j = i * 2; j <= b; j += i)
			{
				prime[j] = true;
				if(j - i>=a && find(j) != find(j-i))//将当前被筛的数与上一个被筛的数合并（第一个被筛的数和质因数本身合并）
				//注意这两个数都要在a~b之间才合并
				{
					f[find(j)]=find(j-i);//合并集合 
					ans--;
				}
			}
		  }
		  else
		  {
			for(int j = i*2; j <= b; j += i)
			{
				prime[j]=true;
			}
		  }
		}		
	}
	return ans;
}


int read()//快读函数 
{
    int k=0,f=1;
	char ch=getchar();
    while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
    while(ch>='0'&&ch<='9')
	{
		k=k*10+ch-'0';
		ch=getchar();
	}
    return k*f;
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr),cout.tie(nullptr);
	
    a= read(),b = read(),p = read();
    
    int ans = b - a + 1;
    
    _rep(i,a,b) f[i] = i;
    
    cout<< get_prime()<<'\n';
    
	
    return 0;
}