【题目描述】

现在给你一些连续的整数，它们是从A到B的整数。一开始每个整数都属于各自的集合，然后你需要进行如下操作。
每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于P的公共质因数，那么把他们所在的集合合并。
反复上述操作，直到没有可以合并的集合为止。
现在caima希望知道，最后有多少个集合。

【输入格式】

一行，三个整数A，B，P。

【输出格式】

一个数，表示最终集合的个数。

只要这集合中的某两个数存在大于等于p的质数即可在同一个集合

线性筛出所有素数，然后将所有大于等于p的素数倍数用并查集合并在一起，把小合并到大，最后看有多少个联通块即可

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
int f[200005],a,b,p,ans;
bool prime[200005];
int find(int x)
{
return (x==f[x])?x:f[x]=find(f[x]);
}
int main()
{
scanf("%d%d%d",&a,&b,&p);
for(int i=1;i<=b;i++) f[i]=i;
for(int i=2;i<=b;i++)
{
if(!prime[i])
{
for(int j=1;j*i<=b;j++)
{
prime[j*i]=1;
if(i>=p)
if(j*i>=a&&j*i<=b)
{
int fx=find(i),fy=find(j*i);
//
cout<<fx<<" "<<fy<<endl;
if(fx==fy) continue;
if(fx>fy) f[fy]=fx;
else f[fx]=fy;
}
}
}
}
for(int i=a;i<=b;i++) if(f[i]==i) ans++;
printf("%d",ans);
}

最后

以上就是勤恳柠檬为你收集整理的【并查集】集合set【题目描述】的全部内容，希望文章能够帮你解决【并查集】集合set【题目描述】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。