题目链接：http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2327
大意：给你一个[A,B]的区间(1<=A<B<=1e12)，给你一个素数P，对于每一个大于等于P的素数，如果区间中有两个数i,j是素数p的倍数，则i,j所在的集合应该合并。初始时每个数都是一个集合，问你最后会有多少个集合。
A, B, P, (1 ≤ A ≤ B ≤ 1e12, B ≤ A + 1e6, 2 ≤ P ≤ B)
思路：注意到B-A<=1e6，所以整个区间长度不超过1e6，则对于大于等于1e6的素数，它在集合中至多只有一个倍数，不会产生合并操作，所以都可以忽略。所以可以筛选1e6内的素数，用1e6的并查集映射[A,B]区间，对于每一个满足条件的素数，它的倍数都应该在一个集合中，直接做合并操作即可。
最后没写出来是因为不知道怎么写从A（1e12）开始的遍历。。。。以后要记住，可以用now=A/p[i]得到第一个小于等于A的p[i]的倍数，那么如果小于，now++就可以得到第一个大于A的倍数了。。。。。。。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> #include <queue> #include <vector> using namespace std; const int maxn=1e6+10; typedef long long ll; ll fa[maxn]; ll find_set(ll x){ return fa[x]==x?x:fa[x]=find_set(fa[x]); } vector<ll>prime; ll A,B,P; int vis[maxn]; ll p[maxn],cnt; void init(){ memset(vis,0,sizeof(vis)); for(int i=2;i<maxn;i++){ if(!vis[i]){ prime.push_back(i); } for(int j=0;j<prime.size();j++){ if(i*prime[j]>=maxn)break; vis[i*prime[j]]=1; if(i%prime[j]==0)break; } } } int main(){ init(); while(scanf("%lld%lld%lld",&A,&B,&P)!=EOF){ cnt=0; for(ll i=0;i<maxn;i++)fa[i]=i; if(P>=1e6){ printf("%lld\n",B-A+1); continue; } int ks=0; for(int i=0;i<prime.size();i++){ if(prime[i]>=P){ ks=i; break; } } for(int i=ks;i<prime.size()&&prime[i]<=B;i++){ ll now=A/prime[i]; if(now*prime[i]<A)now++; ll x=find_set(now*prime[i]-A+1); for(ll j=now;prime[i]*j<=B;j++){ ll temp=find_set(prime[i]*j-A+1); if(temp!=x){ fa[temp]=x; } } } ll ans=0; for(ll i=A;i<=B;i++){ ll temp=i-A+1; if(fa[temp]==temp){ ans++; } } printf("%lld\n",ans); } return 0; }
