题目
思路
并查集+埃氏筛,一开始连通块的个数是\(b-a+1\)个,在筛素数的过程中只要当前素数大于\(p\)就对该素数筛出来的数进行判断,如果不连通并且小的数大于等于\(a\)就合并连通块个数减一,最后的联通块个数就是答案。(具体看代码)
\(Code\)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define MAXN 100001
using namespace std;
int ans,a,b,p;
int fa[MAXN],size[MAXN];
bool prime[MAXN];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Union(int x,int y){
int rootx=find(x),rooty=find(y);
if(rootx==rooty) return;
if(size[rootx]>size[rooty]){
fa[rooty]=rootx;
size[rootx]+=size[rooty];
}else{
fa[rootx]=rooty;
size[rooty]+=size[rootx];
}
}
inline void read(int &T){
int x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
int main(){
read(a),read(b),read(p);
for(int i=a;i<=b;++i){
fa[i]=i;
}
ans=b-a+1;
for(int i=2;i<=b;++i){
if(!prime[i]){
if(i>=p){//如果当前质数大于p才合并
for(int j=i*2;j<=b;j+=i){
if(j-i>=a&&find(j)!=find(j-i)){//将当前被筛的数与上一个被筛的数合并(第一个被筛的数和质因数本身合并),注意这两个数都要在a~b之间才合并
Union(j,j-i);
ans--;
}
prime[j]=1;
}
}else{
for(int j=i*2;j<=b;j+=i){
prime[j]=1;
}
}
}
}
printf("%d\n",ans);
return 0;
}