当前位置: 首页> 房产> 家装 > 东鹏设计家官网_建设网站的企业有哪些_百度安装到桌面_成都关键词自然排名

东鹏设计家官网_建设网站的企业有哪些_百度安装到桌面_成都关键词自然排名

时间:2025/7/11 1:11:40来源:https://blog.csdn.net/2302_79431881/article/details/144812605 浏览次数:0次
东鹏设计家官网_建设网站的企业有哪些_百度安装到桌面_成都关键词自然排名

题目链接:P1621 集合 - 洛谷 | 计算机科学教育新生态

题目难度:普及/提高

解题思路:这个题要求我们在一个区间[A,B]中找出几个集合,集合中的数满足是一个大于等于P的质因数的个数,我们想到了并查集来维护这个集合,初始时候每个数的父亲就是本身,我们明确了求解答案的条件,就是将所有有大于等于P的质因数的一堆数合并起来,统计父亲是自己的个数,我们可以用筛法来求,将所有公共质因数的数在筛法过程中直接合并。最后输出答案即可。

下面奉上代码部分:

#include<bits/stdc++.h>
using namespace std;	
#define _for(i,a,b) for(int i=(a); i<(b); i++)
#define _rep(i,a,b) for(int i=(a); i<=(b); i++)
typedef long long ll;
const int N = 1e5 + 10;
bool prime[N];
int f[N];
int a,b,p;int find(int x)
{if(f[x] != x) f[x] = find(f[x]);return f[x];
} int get_prime()//埃氏筛
{int ans = b - a + 1;//将答案初始化为a~b间数的个数,每合并一次减1就可以了for(int i=2; i<=b; i++){if(!prime[i]){if(i >= p){for(int j = i * 2; j <= b; j += i){prime[j] = true;if(j - i>=a && find(j) != find(j-i))//将当前被筛的数与上一个被筛的数合并(第一个被筛的数和质因数本身合并)//注意这两个数都要在a~b之间才合并{f[find(j)]=find(j-i);//合并集合 ans--;}}}else{for(int j = i*2; j <= b; j += i){prime[j]=true;}}}		}return ans;
}int read()//快读函数 
{int k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;
}int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr),cout.tie(nullptr);a= read(),b = read(),p = read();int ans = b - a + 1;_rep(i,a,b) f[i] = i;cout<< get_prime()<<'\n';return 0;
}

关键字:东鹏设计家官网_建设网站的企业有哪些_百度安装到桌面_成都关键词自然排名

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: