集合 - 题目列表

题意

区间 [a,b] 中每个整数最初各自成集。若两个数拥有不小于 p 的公共质因数，就能合并它们所在的集合。求所有合并结束后的集合数。

思路

不要枚举两个数再分解最大公约数。反过来枚举允许使用的质因数 prime>=p：区间中 prime 的所有倍数都含有这个公共质因数，因此应该属于同一个集合。

具体做法：

用埃氏筛得到 2..b 的所有质数；
对每个不小于 p 的质数，求 [a,b] 中第一个倍数 first；
把其余倍数依次与 first 合并；
初始集合数为 b-a+1，每次真正合并两个不同集合就减一。

若两个集合能通过多步规则连起来，并查集会自动处理这种传递性。

Python 知识

用下标 number-a 保存区间 [a,b]，无需为 0..a-1 浪费并查集空间。
bytearray 每个筛标记只占一个字节，比 Python 布尔对象列表紧凑。
切片赋值 is_prime[start:b+1:prime]=... 一次标记整段倍数，循环工作在底层完成。
nonlocal groups 允许内层 union 修改外层的集合计数。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：Python 容器内存和循环性能注意点。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：按需遍历数值序列的思路。

代码

python

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
45import sys


def main():
    a, b, minimum_prime = map(int, sys.stdin.buffer.read().split())
    parent = list(range(b - a + 1))
    size = [1] * len(parent)
    groups = len(parent)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        nonlocal groups
        x, y = find(x), find(y)
        if x == y:
            return
        if size[x] < size[y]:
            x, y = y, x
        parent[y] = x
        size[x] += size[y]
        groups -= 1

    is_prime = bytearray(b + 1)
    is_prime[2:] = b"\x01" * (b - 1)
    for number in range(2, int(b ** 0.5) + 1):
        if is_prime[number]:
            start = number * number
            is_prime[start:b + 1:number] = b"\x00" * ((b - start) // number + 1)

    for prime in range(minimum_prime, b + 1):
        if not is_prime[prime]:
            continue
        first = (a + prime - 1) // prime * prime
        for multiple in range(first + prime, b + 1, prime):
            union(first - a, multiple - a)

    print(groups)


if __name__ == "__main__":
    main()

cpp

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/**
 * P1621 集合
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXB = 100005;

int fa[MAXB];

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) fa[x] = y;
}

bool is_prime[MAXB];
int a, b, p;

int main() {
    scanf("%d%d%d", &a, &b, &p);
    int n = b - a + 1; // 区间中的整数个数
    for (int i = 0; i < n; ++i) fa[i] = i;

    // 筛法求素数
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= b; ++i) {
        if (is_prime[i]) {
            if ((long long)i * i <= b) {
                for (int j = i * i; j <= b; j += i)
                    is_prime[j] = false;
            }
            // 对每个 ≥p 的素数，合并区间内所有它的倍数
            if (i >= p) {
                int first = (a + i - 1) / i * i; // 区间中第一个 i 的倍数
                for (int j = first + i; j <= b; j += i)
                    unite(first - a, j - a);
            }
        }
    }
    // 统计集合数
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (fa[i] == i) ++ans;
    printf("%d\n", ans);
    return 0;
}

复杂度

筛法约为 $O(b\log\log b)$ 。合并倍数的总次数不超过调和级数规模，结合并查集可写为 $O(b\log\log b+b\alpha(b))$ ，空间复杂度 $O(b)$ 。

总结

从“哪些数对能合并”转成“一个合法质因数能连接哪些倍数”，避免了平方级数对枚举；并查集负责把不同质因数产生的连接继续传递。

集合

目录

题意

思路

Python 知识

代码

复杂度

总结