python/TangDou/AcWing/SearchOrder/1118.md

AcWing 1118. 分成互质组

一、题目描述

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

至少 要分成多少个组？

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

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

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

数据范围 1≤n≤10

输入样例：

6
14 20 33 117 143 175

输出样例：

3

二、实现思路

枚举每个数字，尝试将其放入到某个已有的组中(需保证与此组中其它数字 互质 )，当然，也可以不放入任何一个组中，全新开一个组。

注意 回溯

Code

#include <bits/stdc++.h>

using namespace std;
const int N = 20;
const int INF = 0x3f3f3f3f;
int n, a[N];
int ans = INF;
vector<int> g[N]; // 共几个组，每组都放哪些互质的数字

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

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

void dfs(int u, int len) {
    // 剪枝，剪完后19ms,不剪36ms
    if (len >= ans) return;

    // 枚举完所有数字，结束
    if (u == n + 1) {
        ans = len; // 更新组数最小值,大的等的都被上面的那句剪枝给整回去了
        return;
    }

    for (int i = 0; i < len; i++) { // 枚举前面所有的组
        if (check(a[u], i)) {       // 如果a[u]可以放入i组
            g[i].push_back(a[u]);   // 放进i组
            dfs(u + 1, len);        // 走到下一个数字面前，没有增加组数
            g[i].pop_back();        // 回溯，不入进i组
        }
    }

    // 新开一组
    g[len].push_back(a[u]); // 将a[u]这个数字，放入到len这一组中
    dfs(u + 1, len + 1);    // 走到下一个数字面前，现在的组数加了1个
    g[len].pop_back();      // 回溯，不放入len这一组中　
}

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

    // 第1个数开始,现在0组
    dfs(1, 0);

    // 输出最少组数
    cout << ans << endl;
    return 0;
}