形式化题目

给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$，求一个划分 $S_1 \sqcup S_2 \sqcup \cdots \sqcup S_k = \{1, 2, \dots, n\}$，使得每个组 $S_j$ 内部 任意两个元素对应的数互质：

要求最小化组数 $k$。

约束：$1 \leqslant n \leqslant 10$，$a_i \leqslant 10000$，数值可以重复。

样例

输入为 $6$ 个数 $14, 20, 33, 117, 143, 175$。下面这张图画出了它们之间的冲突关系 （两个数不互质就连一条边）。

graph LR
    n1["14"] --- n2["20"]
    n1 --- n6["175"]
    n2 --- n6
    n3["33"] --- n4["117"]
    n3 --- n5["143"]
    n4 --- n5

凡是连了边的两个数都不能同组。观察这张图：第一组三角形是因为 $\gcd(14,20)=2$、$\gcd(14,175)=7$、$\gcd(20,175)=5$，三个数两两都不互质； 第二组三角形同理（$\gcd(33,117)=3$、$\gcd(33,143)=11$、$\gcd(117,143)=13$）。 答案 $3$ 组的划分之一是 $\{14, 33\},\ \{20, 117\},\ \{143, 175\}$ —— 三个三角形各自只需要分到不同颜色的两个点，剩下一个点可以和另一个三角形里的点同色。 读者可以逐个核对这 $3$ 对都互质。

正解

思路

朴素做法的瓶颈。 最直接的办法是把数一个一个放进组里：对当前数，先尝试已有的每一组 （能放的条件是与组内每个数都互质），都放不进去就新开一组；由于"放哪一组"有多个选择， 必须回溯把所有分支试完，才能取到最小答案。这个枚举是正确的，但它把大量的重复情况算了 很多遍 —— 同一个下标集合 $\{a_2, a_5, a_7\}$ 在不同搜索分支里被反复检查合法性、反复展开， 而且搜索树没有任何结构可以利用，规模随 $n$ 阶乘式增长。

换一个视角：组只由集合决定。 注意"一组数是否合法"只取决于这个集合本身：只要集合内 两两互质就合法，与这些数是按什么顺序、在搜索的哪一步被放进来的完全无关。这说明可以把 "组"从搜索过程里彻底剥离出来，抽象成一个下标集合。

于是把所有下标当成点，把"两个数不互质"当成一条边，得到一张冲突图 $G$：

此时"组内两两互质"恰好就是"组内没有 $G$ 的边"，即组是 $G$ 的一个独立集。 而"把全部点划分成 $k$ 个组"正是"给 $G$ 找一个 $k$-染色"的定义。结论：

答案 $=$ 冲突图 $G$ 的最小染色数（每种颜色对应一组）。

这一步把"分组方案"的枚举换成了"集合覆盖"的枚举，重复子问题立刻显形：只要记住 “覆盖某个集合最少要几组”，就不用再关心之前是怎么走到这个集合的。

预计算独立集。 用位掩码表示下标集合。对每个 $i$ 先算出与它冲突的下标掩码 full[i]。一个集合 $S$ 是否独立，可以拿它的最低位 $v$ 归纳：

从空集（恒独立）开始按掩码从小到大递推，$O(2^n)$ 就把 $2^n$ 个集合的合法性全部算完。

子集 DP。 设 $f(S)$ 为覆盖集合 $S$ 所需的最少组数：

枚举 $T$ 时只保留包含 $S$ 最低位的那些：最优划分中必定有一组包含这个点，把它拎出来作为 "第一组"不会漏掉任何最优解，但能显著减少枚举量。用 t = (t - 1) & S 枚举 $S$ 的全部子集。

以样例为例，取几个关键状态看 DP 表怎么长出来（$f$ 的单位是"组数"）：

最后一行是本题的关键：$f$ 不能只看“这一组能塞多少个数”，而必须把所有合法 $T$ 都试一遍。 以全集为例，取 $T = \{14, 33\}$ 时剩下 $\{20, 117, 143, 175\}$ 只需 $2$ 组（表中已验证）， 而换一个 $T$ 未必能达到同样的效果 —— 所以 $\min$ 不能省。

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 00:30
# update_at: 2026-09-30 00:37

import sys
from functools import cache
from math import gcd

FULL = 0  # 空集合的位掩码，单独命名避免裸写 0 引起歧义


def conflict_mask(value: int, others: list[int]) -> int:
    """与 value 不互质的那些数在 others 里的下标位：这些数不能和它同组。"""
    return sum(1 << j for j, other in enumerate(others) if gcd(value, other) > 1)


def subsets_desc(mask: int) -> list[int]:
    """降序列出 mask 的全部非空子集（标准 t = (t-1) & mask 技巧）。"""
    result: list[int] = []
    t = mask
    while t:
        result.append(t)
        t = (t - 1) & mask
    return result


def min_groups(n: int, values: list[int]) -> int:
    """把 n 个数分成最少的组，使每组内任意两数互质（等价于冲突图的最少染色数）。

    冲突图：i -- j 当且仅当 gcd(a_i, a_j) > 1。组内两两互质就是独立集，
    所以答案 = 覆盖全部点的最少独立集个数 = 冲突图的最小染色数。
    按子集 DP：f[S] = 1 + min{ f[S \\ T] : T ⊆ S 且 T 是独立集 }。
    """
    # full[i]：与 a_i 冲突（gcd > 1）的下标位，用来快速判定"能否同组"
    full = [conflict_mask(values[i], values) for i in range(n)]

    # independent[S]：S 内部两两互质。去掉最低位 v 的点后，只需 v 与剩余部分都不冲突
    independent = bytearray(1 << n)
    independent[FULL] = 1
    for s in range(1, 1 << n):
        low = s & -s
        v = low.bit_length() - 1
        rest = s ^ low
        independent[s] = independent[rest] and not (full[v] & rest)

    # 每个集合的独立子集表：只枚举一次，DP 里直接查表
    ind_subsets = [subsets_desc(s) for s in range(1 << n)]

    @cache
    def best(s: int) -> int:
        """覆盖集合 s 所需的最少组数。"""
        if s == FULL:
            return 0
        low = s & -s  # 最优划分中必有一组包含 s 的最低位的点，只需枚举含它的独立集
        return 1 + min(
            best(s ^ t) for t in ind_subsets[s] if t & low and independent[t]
        )

    return best((1 << n) - 1)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    values = [next(data) for _ in range(n)]
    print(min_groups(n, values))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 23:24
 * update_at: 2026-10-04 23:24
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 11;
const int MAXSTATE = 1 << MAXN; // n <= 10，子集掩码最多 2^10 种

typedef long long ll;

ll n;
ll a[MAXN];             // a[i]：第 i 个数（下标从 0 开始，与掩码位对应）
ll conflict[MAXN];      // conflict[i]：与第 i 个数不互质（冲突）的下标掩码
ll f[MAXSTATE];         // f[S]：把下标集合 S 划分成合法组所需的最少组数
char independent[MAXSTATE]; // independent[S]：S 内部是否两两互质（0/1），用 char 控制内存

// 求 x 与 y 是否互质。
bool coprime(ll x, ll y) {
    return __gcd(x, y) == 1;
}

// 预处理每个数的冲突掩码，以及全部 2^n 个集合的"是否独立"。
void build_conflict() {
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (i != j && !coprime(a[i], a[j])) {
                conflict[i] |= (1LL << j); // i 与 j 不互质，不能同组
            }
        }
    }

    independent[0] = 1; // 空集独立
    for (ll S = 1; S < (1LL << n); S++) {
        // 取最低位 v：S 独立 <=> S 去掉 v 后独立，且 v 与 S 剩余部分无冲突
        ll v = 0;
        while (!(S & (1LL << v))) v++;
        ll rest = S ^ (1LL << v);
        independent[S] = (independent[rest] && (conflict[v] & rest) == 0) ? 1 : 0;
    }
}

void solve() {
    build_conflict();

    f[0] = 0; // 空集不需要任何组
    for (ll S = 1; S < (1LL << n); S++) {
        // 最优划分中必有一组包含 S 的最低位，枚举包含最低位的独立子集 T 作为第一组
        ll low = 0;
        while (!(S & (1LL << low))) low++;

        f[S] = LLONG_MAX;
        // 枚举 S 的所有子集 t（必含最低位 low）
        for (ll t = S; t > 0; t = (t - 1) & S) {
            if (!(t & (1LL << low))) continue;
            if (!independent[t]) continue; // 同一组内必须两两互质
            if (f[S ^ t] + 1 < f[S]) {
                f[S] = f[S ^ t] + 1;
            }
        }
    }

    cout << f[(1LL << n) - 1] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }

    solve();

    return 0;
}

复杂度

• 冲突掩码 $O(n^2 \log V)$，其中 $V \leqslant 10^4$ 是数值上界；
• 独立集表 $O(2^n)$；
• 子集枚举与 DP 合计 $O(3^n)$（$\sum_{S} 2^{|S|} = 3^n$），记忆化保证每个状态只算一次；
• 总时间 $O(n^2 \log V + 3^n)$，$n = 10$ 时 $3^{10} = 59049$；
• 空间 $O(3^n)$：independent 占 $2^n$ 字节，ind_subsets 存下全部子集共 $3^n$ 个整数 （$n = 10$ 时约 $5.9$ 万个，可接受）。

总结

关键在于把"怎么分组"翻译成"给冲突图染色"：不互质连边，一组就是独立集，答案就是最小染色数。 有了这个模型，原本靠回溯硬搜的问题变成 $2^n$ 个子集上的覆盖 DP，每个状态只依赖集合本身， 重复子问题被完全消除。$n \leqslant 10$ 保证 $O(3^n)$ 足够快；数值范围小，冲突关系直接用 math.gcd 两两比较即可，不需要分解质因数。