写在前面,
什么是团, 最大团, 极大团

题目

给定 n 个正整数，将它们分组，使得每组中任意两个数互质。
至少要分成多少个组？
输入格式
第一行是一个正整数 n。
第二行是 n 个不大于10000的正整数。
输出格式
一个正整数，即最少需要的组数。
数据范围
1≤n≤10
输入样例：
6
14 20 33 117 143 175
输出样例：
3

分析

1.根据题意剖析出最大团模型:

• 互质就是一条无向边, 每一组就是一个团, n个数就是一个n个节点的无向图
• 在每一组中的每个数都两两互质满足团的特性(完全图 -> 图内的各个节点两两之间都有一条边)
• 题目要求至少多少组 -> 每一组的元素尽可能的多 -> 可求最大团

2.多情况问题 -> 爆搜枚举求最优解
比如我们当前放入这个数和后面所有的数都不互质, 但是紧接着它后面的一个可选择放入的数与其后面所有的数都互质，说明这个数应该被拿出来, 而把后面那个数放进去

3.搜索顺序

• 每一组将所有互质的数全部选进去
• 每新开一组就从头开始搜

AC代码

/*
input:
10
783 399 861 672 2952 7542 1971 2511 8568 6969

out:
10
*/

#include <iostream>

using namespace std;

int n;
int p[N]; // 存数
int group[N][N]; // 最多可能有N个组, 每个组可能有N个数 存的是数的序号(保证可以连续性访问)
bool st[N];
int res = N; // 组数的最大值是n个数两两互质

int gcd (int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check (int u, int v, int i)
{
    for(int j = 0 ; j < v ; j ++ )
        if(gcd(p[group[u][j]], p[i]) > 1) return 0;
    return 1;
}

/*
u -> 第几组
v -> 第几组中的第几个数
w -> n个数我用了多少个数
x -> 当前从哪个序列编号开始找下一个互质的数放入组中
*/
void dfs(int u, int v, int w, int x)  // 递归指数型枚举
{
    if(u >= res) return ;
    if(w == n) 
    {
        res = u;
        return ;  // 终点时刻要不要这个return都可以
    }

    /*
    页首的样例不加flag会T(还是可以跑出正确答案但是要慢6倍左右) 
    因为不加flag的话在回溯的过程中会多回溯很多次第86行(本来不需要回溯的)
    */
    bool flag = 1;  
    for(int i = x ; i < n ; i ++ )
        if(!st[i] && check(u, v, i))
        {
            group[u][v] = i;
            st[i] = 1;
            flag = 0;

        dfs(u, v + 1, w + 1, i + 1);

            st[i] = 0;
        }

        if(flag) dfs(u + 1, 0, w, 0); 
        // 1. w不变因为我i还没有放进去 2. x == 0因为开辟一个新的组之后我们又从头开始找数了
}

int main ()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++ ) cin >> p[i];

    dfs(1, 0, 0, 0);

    cout << res << endl;

    return 0;
}

拓展：最大团算法的优化