莫欺少年穷，修魔之旅在这开始—>算法提高课题解

保姆级注释，看不懂你炸我

思路：

1. 枚举所有数字，观察是否有数字是否可以入当前组，如果没有开新组
2. 如果当前数字可以入组，入组后继续观察是否还有新的数字可以入组
3. 不要忘了回溯需要恢复现场

#include <bits/stdc++.h>

using namespace std;

const int N = 11;

int n;
int p[N];
int group[N][N];
bool st[N];
int ans = N;

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

//判断当前数字是否可以与当前组互质
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;
}

//当前枚举到第u组，第u组中已确定gc个，所有数已确定tc个，枚举到所有数中的p[start];
void dfs(int u, int gc, int tc, int start) {
    //分组数大于等于ans，直接return
    if (u >= ans) return;

    //所有数字都已入组
    if (tc == n) ans = u;

    //判断是否有数字能与当前组互质
    bool flag = false;
    for (int i = start; i < n; i++)
        if (!st[i] && check(group[u], gc, i)) {
            //记录当前数字
            st[i] = true;

            //把当前数字入组
            group[u][gc] = i;

            //枚举下一个能入当前组的数字
            dfs(u, gc + 1, tc + 1, i + 1);

            //恢复现场，不要当前数字
            st[i] = false;

            //有数字能与当前组互质
            flag = true;
        }

    //没有数字能与当前组互质，开新组
    if (!flag) dfs(u + 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;
}