集合

题目描述

Caima 给你了所有 $[a,b]$ 范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数，如果这两个整数拥有大于等于 $p$ 的公共质因数，那么把它们所在的集合合并。

重复如上操作，直到没有可以合并的集合为止。

现在 Caima 想知道，最后有多少个集合。

输入格式

一行，共三个整数 $a,b,p$，用空格隔开。

输出格式

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

样例 #1

样例输入 #1

10 20 3

样例输出 #1

7

提示

样例 1 解释

对于样例给定的数据，最后有 { 10 , 20 , 12 , 15 , 18 } , { 13 } , { 14 } , { 16 } , { 17 } , { 19 } , { 11 } {10,20,12,15,18},{13},{14},{16},{17},{19},{11} {10,20,12,15,18},{13},{14},{16},{17},{19},{11} 共 $7$ 个集合，所以输出应该为 $7$。

数据规模与约定

• 对于 $80\%$ 的数据，$1\le a\le b\le 10^3$。
• 对于 $100$ 的数据，$1\le a\le b\le 10^5,2\le p\le b$。

并查集+线性筛

#include<bits/stdc++.h>
using namespace std;
int f[100010],primes[100010],cnt;
bool st[100010];
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
f[find(x)] = find(y);
}
int main() {
int a, b, p;
cin >> a >> b >> p;
int ans = b - a + 1;
for (int i = a; i <= b; i++)f[i] = i;
for (int i = 2; i <= b; i++) {
if (!st[i])primes[cnt++] = i;
for (int j = 0; primes[j] <= b / i; j++) {
st[primes[j]*i] = true;
if (i % primes[j] == 0)break;
}
}
for (int i = 0; i < cnt; i++) {
if (primes[i] >= p) {
int t = (a - 1 + primes[i]) / primes[i] * primes[i];
for (int j = t + primes[i]; j <= b; j += primes[i]) {
if (find(t) != find(j)) {
ans--;
merge(t, j);
}
}
}
}
cout << ans;
}

最后

以上就是典雅花卷为你收集整理的P1621 集合集合的全部内容，希望文章能够帮你解决P1621 集合集合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。