P1621 集合

P1621 集合 – 洛谷

心路历程

这题需要用到质数筛选, 这并不难, 让我比较意外的是这题居然把唯一分解定理用的如此巧妙, 通过乘积直接找准

[

a

,

b

]

[a, b]

[a,b] 上的所有合数进行合并操作

题目描述

Caima 给你了所有

[

a

,

b

]

[a,b]

[a,b] 范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数，如果这两个整数拥有大于等于

p

p

p 的公共质因数，那么把它们所在的集合合并。

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

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

输入格式

一行，共三个整数

a

,

b

,

p

a,b,p

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

7 个集合，所以输出应该为

7

7

7。

数据规模与约定

• 对于 $80\%$
• 对于 $100\%$

解析

#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<vector>
using namespace std;

int a, b, p;
unordered_map<int, int> parent;
unordered_set<int> roots;
vector<int> primes;
vector<int> isPrime;

void EulerSieve(){
// 唯一分解定理, 将 >= p的质因子筛出来
for(int i = 2; i <= b; i++){
if(isPrime[i]){
// 是质数就装入
primes.push_back(i);
}
// 然后将以i为因子的质因子倍合数晒出来
for(int j = 0; j < primes.size(); j++){
if(primes[j] * i > b) break;
isPrime[primes[j] * i] = 0;
if(i % primes[j] == 0) break;
}
}
}
// 获取根结点
int getRoot(int id){
if(parent[id] == id) return id;
return parent[id] = getRoot(parent[id]);
}
void merge(int x, int y){
int xRoot = getRoot(x);
int yRoot = getRoot(y);
if(xRoot != yRoot){
parent[xRoot] = getRoot(y);
roots.erase(xRoot);
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> a >> b >> p;
// 初始化并查集和根集合
for(int i = a; i <= b; i++){
parent[i] = i;
roots.insert(i);
}
// 用质数筛法将[p, b]区间内的质数全部筛出来, 并放入数组
isPrime.resize(b + 1, 1);
EulerSieve();
// 然后根据唯一分解定理, 将[a, b]区间内的数尽量合并
for(int i; i < primes.size(); i++){
if (primes[i] < p) continue;
// 将所不小于的p质数遍历一边, 然后利用唯一分解定理求出在[a, b]范围内的所有合数合并
int times = 1;
while(primes[i] * times < a) times++;
// 此刻primes[i] * times为一个大于a的合数
// 然后将所有以primes[i]为质因子且在[a, b]范围内的合数所在集合合并
for(int j = times + 1; primes[i] * j <= b; j++){
merge(primes[i] * (j – 1), primes[i] * j);
}
}
// 最后计算合并集合数
cout << roots.size();
return 0;
}