洛谷-1621 集合 HQG_AC的博客

解法：并查集

我们枚举所有大于等于p的质因数，之后枚举这个数的倍数，将这些数所在的聚合都用并查集并起来。

时间复杂度：O(nlognα(n))

#include
using namespace std;
int A,B,n,i,j,p[100010],dad[100010],P,ans,vis[100010];
int find(int x){return dad[x]==x?x:dad[x]=find(dad[x]);
}
void merge(int x,int y){dad[find(x)]=find(y);
}
int main(){scanf("%d%d%d",&A,&B,&P);for(i=A;i<=B;i++)dad[i]=i;for(i=2;i<=B;i++)if(!vis[i]){p[++n]=i;for(j=i+i;j<=B;j+=i)vis[j]=1;}for(i=1;i<=n;i++)if(p[i]>=P)for(j=p[i]*2;j<=B;j+=p[i])if(j-p[i]>=A)merge(j,j-p[i]);for(i=A;i<=B;i++)if(dad[i]==i)ans++;printf("%d\n",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！