题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int N = 10;
int group[N][N];
int n;
bool st[N];
int nums[N];
int res = 10;

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

bool check(int g, int gc, int i)
{
    for (int k = 0; k < gc; k ++)
    {
        if (gcd(nums[group[g][k]], nums[i]) > 1)  return false;
    }
    return true;
}

void dfs(int g, int gc, int tc, int start)//组合型的，与顺序无关，所以加一个start；
{
    if (g >= res) return;
    if (tc == n)
    {
        res = g;
        return;
    }

    bool flag = true;
    for (int i = start; i < n; i ++)
    {
        if (!st[i] && check(g, gc, i))
        {
            st[i] = true;
            group[g][gc] = i;
            dfs(g, gc + 1, tc + 1, i + 1);
            st[i] = false;

            flag = false;
        }
    }
    if (flag) dfs(g + 1, 0, tc, 0);

}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> nums[i];

    dfs(1, 0, 0, 0);
    cout << res;
    return 0;


}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla