整数合并

57 阅读 0 评论 38 点赞

我是靠谱客的博主忧心电话，最近开发中收集的这篇文章主要介绍整数合并，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

P1504 - 整数合并

Description

现在给你一些连续的整数，它们是从 A 到 B 的整数。一开始每个整数都属于各自的集合，然后你需要进行如下操作：
每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于 P 的公共质因子，那么把他们所在的集合合并。
反复上述操作，直到没有可以合并的集合为止。
现在，小 X 想知道，最后有多少个集合。

Input

一行，三个整数 A,B,P

Output

一个数，表示最终集合的个数。

Sample Input

10 20 3

Sample Output

7

Hint

样例解释：
解释： {10 ， 20 ， 12 ， 15 ， 18} ， {11}，{13} ， {14} ， {16} ， {17} ， {19}
【数据规模】
B<=1000. 80%数据
A<=B<=100000; 2<=P<=B

可以先用欧拉筛把小于ｂ的素数都筛出来，然后每个素数的倍数肯定都是一个集合的，
然后某个数的素因数如果不止一个，那还可以和别的集合合并成一个集合。

枚举素数的时候可以搞一个标记，表示这个素数的集合对答案有没有贡献，
若在枚举这个素数的倍数的时候发现某个数是已经有找出来的质因数，
那么这个素数集合肯定可以和前面的那个素数集合合并，
所以这个素数集合对答案是没有贡献的。在最后还要把答案加上那些没有找到质因子的数的数量。
具体实现看代码

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define maxn 100010
15 using namespace std;
16 bool bj[maxn];
17 int su[maxn];
18 vector<int>from[maxn];
19 int main()
20 {
21
freopen("!.in","r",stdin);
22
freopen("!.out","w",stdout);
23
int a,b,p,sum=0;
24
scanf("%d%d%d",&a,&b,&p);
25
for(int i=2;i<=b;i++){
26
if(bj[i]==0) su[++sum]=i;
27
for(int j=1;j<=sum;j++){
28
if(su[j]*i>b) break;
29
bj[su[j]*i]=1;
30
if(i%su[j]==0) break;
31 
}
32 
}
33
int ans=0;
34
for(int i=1;i<=sum;i++){
35
if(su[i]<p) continue;
36
int y=a/su[i]*su[i];
37
while(y<a) y+=su[i];
38
int f=1;if(y>b) f=0;
39
while(y<=b){
40
if(from[y].size()>0) f=0;
41
from[y].push_back(i);
42
y+=su[i];
43 
}
44
ans+=f;
45 
}
46
for(int i=a;i<=b;i++) if(from[i].size()==0) ans++;
47
printf("%d",ans);
48
return 0;
49 }