这是18/2/23 YCOI第二题的题解。
题目是这样的：
【题目描述】
现在给你一些连续的整数，它们是从 A 到 B 的整数。一开始每个整数都属于各自的集合，然后你需要进行一下的操作： 每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于 P 的公共质因数，那么把它们所在的集合合并。 反复如上操作，直到没有可以合并的集合为止。 现在ENOR想知道，最后有多少个集合。
【输入文件】
一行，三个整数 A,B,P。
【输出文件】
一个数，表示最终集合的个数。
【样例输入】
1
210 20 3
【样例输出】
1
27
【样例解释】
{10,20,12,15,18}，{13}，{14}，{16}，{17}，{19}。
【数据范围】
A≤B≤100000； 2≤P≤B。
有 80%的数据 B≤1000。
【题解】
首先，一看操作就是并查集，先写一个并查集的模板……
P.S：如果不知道什么是并查集，可以去我的博客里找模板……
接着，要找质因数，那就需要素数筛法，我这里用的是线性筛法，复杂度O（n），用Eratosthenes 筛法应该也没什么大问题，不过我没尝试。
P.S：如果不知道素数筛法怎么写，去我的博客找模板……
那么找到b以内的素数之后，从第一个素数开始枚举，如果该素数(以下记为pp)大于等于p，就开始操作：在区间[a,b]中找到最小的、是pp的倍数的数。这变成了一个数学问题，我们先看a里面有多少个pp，那就是a/pp个，那么(a/pp)*pp就是不大于a的最大的i的倍数。这时加判定，如果(a/pp)*pp＜a，那就把(a/pp)*pp加上pp，否则不变。这样就得到了区间[a,b]中找到最小的、是pp的倍数的数。
找到这个数之后，记为temp，循环for(int i=temp;i<=b;i+=pp)，每次把这个值与temp合并，就把含质因数pp的所有数合并完成了。
然后计算合并次数，jay提出的想法是把并查集Union函数设成int类型，如果进行了合并操作（即祖先不同），就return 1，否则return 0。这样先把次数设成最大，也就是int ans=b-a+1，然后每次调用Union时写成ans-=Union(x,y)，就解决了计数问题。
P.S:原题名字叫set，我想了很长时间没想明白set的意义是什么……然后我下面AC代码就用merge代表这道题了……
【AC代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//LJM
T2 merge
#include<cstdio>
#define MAXN 100010
using namespace std;
int fa[MAXN];
//父节点
int a,b,p;
//下面是素数筛法用到的数组
bool check[MAXN]={0};
int prime[MAXN]={0};
int tot=0;
//下面两个并查集
int Find(int x) {
return fa[x]==x?x:fa[x]=Find(fa[x]);
}
int Union(int x,int y) {
int xxx=Find(x);
int yyy=Find(y);
if(xxx!=yyy) {
fa[xxx]=yyy;
return 1;
}
return 0;
}
//素数的线性筛法
void getprime() {
//我获取的是2到b+1的素数，实际上2到b就可以
for(int i=2; i<=b+1; i++) {
if(!check[i]) prime[tot++]=i;
for(int j=0; j<tot&&i*prime[j]<=b+1; j++) {
check[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main() {
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
scanf("%d%d%d",&a,&b,&p);
int ans=b-a+1;
//计数初始化成一共多少个元素，然后合并一次-1
for(int i=a; i<=b; i++) {
//初始化每个节点的父亲设成自己
fa[i]=i;
}
getprime();
for(int i=0;i<tot;i++){
if(prime[i]>=p){
//找[a,b]内最小的是该素数倍数的数，记为temp
int temp=a/prime[i]*prime[i];
if(temp<a) temp+=prime[i];
for(int j=temp;j<=b;j+=prime[i]){
ans-=Union(temp,j);
}
}
}
printf("%dn",ans);
return 0;
}最后
以上就是暴躁指甲油最近收集整理的关于(并查集、素数筛法)合并元素 题解这是18/2/23 YCOI第二题的题解。的全部内容，更多相关(并查集、素数筛法)合并元素内容请搜索靠谱客的其他文章。
发表评论 取消回复