题解 P1621 【集合】

· · 题解

题目链接

这个题要求我们在一个区间[A,B]中找出几个集合，集合中的数满足是一个大于等于P的质因数的个数。

1.看到集合这个定义，我们瞬间会想到用并查集来维护这个集合，那么对于这个集合，他满足一个性质，就是如果我们，起始的时候初始化每一个数的父亲都是自己，那么每一个集合中有且只有一个数的父亲是自己。根据这个性质，我们明确了求解答案的条件，就是将所有有大于等于P的质因数的一堆数合并起来，统计父亲是自己的个数。

2.那么我们如何将有同样大于等于P的质因数找出来呢，我们选择通过中转的方式来进行，即如果我们找到1个大于等于P的质因数是这个数的因数，那么我们把这两个数放在一个集合中，最终与这个数有同样质因数的数也会在这个集合中。

3.那么我们应该如何找这些质因数呢，我们自然而然的想到通过筛法进行预处理，这次我们采用的是欧拉筛法，时间复杂度为O(N）。

关于欧拉筛？

    for(int i=2;i<=B;i++)
    {
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&p[j]*i<=B;j++)
        {
            vis[p[j]*i]=1;
            if(!i%p[j]) break;
        }
     }

把这个代码贴出来：

#include <bits/stdc++.h>
#define N 200010
using namespace std;
int ans;
int A,B,P,cnt,p[N],vis[N];
int fa[N];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    int x1=find(x);
    int y1=find(y);
    if(x1==y1) return;
    fa[x1]=y1;
}
int main()
{
    cin>>A>>B>>P;
    for(int i=A;i<=B;i++) fa[i]=i; 
    for(int i=2;i<=B;i++)
    {
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&p[j]*i<=B;j++)
        {
            vis[p[j]*i]=1;
            if(!i%p[j]) break;
        }
     } 
     for(int i=1;i<=cnt;i++)
     if(p[i]>=P)
     {
        int t=(A+p[i]-1)/p[i]*p[i];//上取整 
        for(int j=t+p[i];j<=B;j+=p[i])
        merge(t,j);
     }
     for(int i=A;i<=B;i++)
     {
        if(fa[i]==i) ans++;
     }
     cout<<ans;
}

完结撒花。