题目描述

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

至少要分成多少个组？

输入格式
第一行是一个正整数 n。

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

输出格式
一个正整数，即最少需要的组数。

数据范围
1≤n≤10

输入样例：
6
14 20 33 117 143 175
输出样例：
3

算法dfs，按数枚举 时间复杂度O(?) 20ms

直接爆搜

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 15;

int a[N],n,res=N;

vector<int> g[N];

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

bool check(int num,int x)
{
    for(auto t:g[num])
    {
        if(gcd(t,x)>1)
            return false;
    }

    return true;
}


void dfs(int u,int len)
{
    if(len>=res) return ;

    if(u==n)
    {
        res=len;
        return;
    }

    for(int i=0;i<len;i++)
        if(check(i,a[u]))
        {
            g[i].push_back(a[u]);   
            dfs(u+1,len);
            g[i].pop_back();
        }

    g[len].push_back(a[u]);
    dfs(u + 1,len+1);
    g[len].pop_back();

}

int main(){

    cin >> n;

    for(int i=0;i<n;i++) cin >> a[i];

    dfs(0,0);

    cout << res << endl;

    return 0;
}