AcWing 1118. 分成互质组

题目传送门

#include 

using namespace std;
const int N = 20;
const int INF = 0x3f3f3f3f;
int n, a[N], ans = INF;
vector g[N];

//最大公约数，辗转相除法
inline int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

//枚举c组中每一个数字，判断是否与u互质
inline bool check(int u, int c) {
    for (int i = 0; i < g[c].size(); i++)
        if (gcd(g[c][i], u) > 1) return false;
    return true;
}

void dfs(int step, int len) {
    //可以考虑加一下剪枝，剪完后19ms,不剪36ms
    if (len >= ans) return;
    if (step == n + 1) {
        ans = min(ans, len);
        return;
    }
    for (int i = 0; i < len; i++) {
        if (check(a[step], i)) {
            g[i].push_back(a[step]);
            dfs(step + 1, len);
            g[i].pop_back();
        }
    }
    // len是当前待操作位置，而不是len+1是待操作位置，这里需要注意一下
    g[len].push_back(a[step]);
    dfs(step + 1, len + 1);
    g[len].pop_back();
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //第1个数开始,现在的组数是0组
    dfs(1, 0);
    //输出最少组数
    cout << ans << endl;
    return 0;
}