<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

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

至少要分成多少个组？

输入格式

第一行是一个正整数 $n$。

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

输出格式

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

数据范围

$1 \\le n \\le 10$

输入样例：

6
14 20 33 117 143 175

输出样例：

3

思路

我们暴搜每一个物品分别放入哪一组，并递归。
这里需要注意我们可以新开一个组。
数据范围只有$10$，所以时间复杂度是小于$O(10^{10})$的，所以能过。
数据比较水，也过了。

代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 20;
int n;
int a[N];
vector <int> g[N];
int ans = 2e9,len;
int gcd (int a,int b) {
    if (!b) return a;
    return gcd (b,a % b);
}
bool check (int u,int t) {
    for (int x : g[u]) {
        if (gcd (x,t) != 1) return false;
    }
    return true;
}
void dfs (int u) {
    if (u > n) {
        ans = min (ans,len);
        return ;
    }
    for (int i = 1;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 ();
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    dfs (1);
    cout << ans << endl;
    return 0;
}