题目

给定 n 个正整数，将它们分组，使得每组中任意两个数互质。

至少要分成多少个组？

输入格式

第一行是一个正整数 n。

第二行是 n 个不大于10000的正整数。

输出格式

一个正整数，即最少需要的组数。

数据范围

1 ≤ n ≤ 10

输入样例：

6
14 20 33 117 143 175

输出样例：

3

解题思路：

①按组爆搜，往最后一个组添加数，直到不符合组内任意两个数互质；

②新开一个组，重复①；

注意搜索顺序：按数字的编号从小到大的顺序搜索，避免重复搜索。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 12;

int n;
int p[N], group[N][N];//p是待加入数组，group是互质数组，group存的是数的编号而非数值
bool st[N];
int ans = N;

//求最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

//判断数字p[i]与组内其他数是否互质
bool check(int group[], int gc, int i)
{
    for (int j = 0; j < gc; j ++)
        if(gcd(p[group[j]],p[i]) > 1)
            return false;

    return true;
}

/*  爆搜，g是已有组的数量，gc是当前组已有数的数量，
    tc是以使用过的数的数量，start是待搜索数的起始编号
*/
void dfs(int g, int gc, int tc, int start)
{
    if (g >= ans) return ;//剪枝优化
    if (tc == n)  ans = g;//所有数已经搜索完毕

    bool flag = true;//判断是否要开一个新数组
    for (int i = start; i < n; i ++)
    {
        if(!st[i] && check(group[g], gc, i))
        {
            st[i] = true;
            group[g][gc] = i;
            dfs(g, gc + 1, tc + 1, i + 1);
            st[i] = false;//回溯
            flag = false;
        }
    }
    if(flag) dfs(g + 1, 0, tc, 0);
}

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

    dfs(1, 0, 0, 0);

    cout << ans << endl;

    return 0;
}