P1621 集合
题目描述
现在给你一些连续的整数，它们是从A到B的整数。一开始每个整数都属于各自的集合，然后你需要进行一下的操作：
每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于P的公共质因数，那么把它们所在的集合合并。
反复如上操作，直到没有可以合并的集合为止。
现在Caima想知道，最后有多少个集合。
输入输出格式
输入格式：一行，三个整数A,B,P。
【数据规模】
A≤B≤100000；
2≤P≤B。
输出格式：一个数，表示最终集合的个数。
输入输出样例
输入样例#1：
10 20 3
输出样例#1：
7
说明
有80%的数据B≤1000。
样例解释{10,20,12,15,18}，{13}，{14}，{16}，{17}，{19}，{11}。
首先打出[p,b]之间的素数表
然后枚举素数p
找到大于等于a的第一个p的倍数，将它与其余b以内的p的倍数合并即可
1 #include <bits/stdc++.h> 2 inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();if(c == '-')x = -x;} 3 const int INF = 0x3f3f3f3f; 4 const int MAXN = 100000 + 10; 5 6 int a,b; 7 int prime[MAXN],bp[MAXN],cnt,p; 8 9 inline void makep(int n) 10 { 11 for(int i = 2;i <= n;i ++) 12 { 13 if(!bp[i])prime[++cnt] = i; 14 15 for(int j = 1;j <= cnt;j ++) 16 { 17 if(i * prime[j] > n)break; 18 bp[i * prime[j]] = 1; 19 if(i % prime[j] == 0)break; 20 } 21 } 22 int tmp = cnt;cnt = 0; 23 for(int i = 1;i <= tmp;i ++) 24 if(prime[i] >= p)prime[++cnt] = prime[i]; 25 } 26 27 int fa[MAXN]; 28 29 int find(int x) 30 { 31 return x == fa[x] ? x : fa[x] = find(fa[x]); 32 } 33 34 void merge(int a, int b) 35 { 36 int x = find(a);int y = find(b); 37 fa[x] = y; 38 } 39 40 int bb[MAXN]; 41 42 int main() 43 { 44 read(a);read(b);read(p); 45 makep(b); 46 for(int i = a;i <= b;++ i)fa[i] = i; 47 for(int i = 1;i <= cnt;++ i) 48 { 49 int k = prime[i]; 50 while(k < a)k += prime[i]; 51 for(int j = k;j <= b;j += prime[i]) 52 { 53 merge(k, j); 54 } 55 } 56 int ans = 0; 57 for(int i = a;i <= b;++ i) 58 { 59 int x = find(i); 60 if(!bb[x])ans ++,bb[x] = 1; 61 } 62 printf("%d", ans); 63 return 0; 64 }