[AcWing 1118] 分成互质组

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 50 + 10;

int n;
int a[N];
int len, ans = 1e9;
vector<int> g[N];

// 判断数字y能否放到第k组
bool inline check(int k, int y)
{
    for (auto& x : g[k])
        if (__gcd(x, y) > 1)
            return false;
    return true;
}

void dfs(int u)
{
    // 全部分完组或组的个数已经超过ans
    if (u == n || len >= ans) {
        ans = min(ans, len);
        return;
    }
    // 放到前面的组中
    for (int i = 0; i < len; i ++)
        if (check(i, a[u])) {
            g[i].push_back(a[u]);
            dfs(u + 1);
            g[i].pop_back();
        }
    // 放到新的一组
    g[len ++].push_back(a[u]);
    dfs(u + 1);
    g[-- len].pop_back();
}

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    dfs(0);
    cout << ans << endl;
}

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

    solve();

    return 0;
}