P1621 集合

题目链接：https://www.luogu.com.cn/problem/P1621

思路

发现1e5/2+ 1e5/3 + 1e5/5+1e5/7+....的结果不到1e6，所以可以直接采用暴力，对于每个质因数P把在[L,R]区间的倍数join一下就行

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int L,R,p;
bool vis[maxn];
int P[maxn/10],tail;
int fa[maxn];
void initP(int N){
    for(int i = 2; i <=N; i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0; P[j] <= N / i; j++){
            vis[P[j] * i] = true;
            if(i % P[j] == 0) break;
        }
    }
}
int find(int x){
    return fa[x] == x? x: fa[x] = find(fa[x]);
}
void join(int x,int y){
    fa[find(x)] = fa[find(y)];
}
int main(){
    // debug;
    ios;
    initP(100010);
    cin>>L>>R>>p;
    for(int i = L;i<=R;i++) fa[i] = i;
    for(int i = 0;i<tail;i++){
        if(P[i]<p) continue;
        for(int j = R/P[i]-1;j*P[i]>=L;j--){
            join(j*P[i],(j+1)*P[i]);
        }
    }
    int ans = 0;
    for(int i = L;i<=R;i++) ans += (find(i) == i);
    cout<<ans<<'\n';

    return 0;
}