$$\color{Red}{分成互质组【最详细的解析和优化(参数含义挖掘)】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

至少要分成多少个组？

输入格式

第一行是一个正整数 n。

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

输出格式

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

数据范围

1 ≤ n ≤ 10

输入样例：

6
14 20 33 117 143 175

输出样例：

3

这题最好先理解 递归实现组合型枚举 这题更容易透彻理解

思路

首先这道题我们为了得到两个数是否互质，需要应用欧几里得算法。且为了分成互质组，我们当然要遍历每组所有元素。

其次这道题我们能在最后一组能放下的情况下，就一定要放到最后一组组，而不是新开组，这是贪心的思路，但是不是任何题或者任何情况都能应用的。

是需要进行证明的： 假设开新组才能搜到最优解，当答案求出来的情况，显然把放入新组的那个元素，放回原本的组不影响答案，且达成了此时不开新组，即继续在更少的组进行枚举，理论上也算是剪枝的思想。

重点在于先理解下标和个数的关系，下标从0开始，所以Count的形参既能代表目前的数量，也能代表下一部枚举的Index。

为了满足我们所说的组合型枚举，也需要加入一个形参start，为了记录可以进行选择的起点下标，然后进入for循环进行依次组合遍历。同时因为我们使用了组合型枚举的思路，和之前组合数枚举这题 不同的是，我们这道题需要把所有的数都分组存放，所以为了进入到下一层dfs能用到所有的数字，需要一个st[]数组设置是否已经使用这个数字。

• @param gIndex 当前枚举的 下标为gIndex的组
• @param gCount 目前 gIndex 下标的组内元素个数 同时也相当于下一个可存入元素的下标值【下标从0开始】
• @param numCount 目前 已经枚举 数字的个数 同时也相当于要进行判断第 numCount 下标的数【下标从0开始】
• @param start 使组合型枚举保持唯一排列顺序 将要判断枚举数的起点下标

一旦能放入当前组，我们下次放为了达成组合型枚举即不把相同的组合但不同的排列的情况计入浪费时间，故我们这里下层dfs的start 应该设置为 i + 1 即从当前挑选的下一个数开始。

java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N = 15, n, ans = N;
    static int[] nums = new int[N];
    static int[][] group = new int[N][N];
    static boolean[] st = new boolean[N];

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

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

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    /**
     * @param gIndex   当前枚举的 下标为gIndex的组
     * @param gCount   目前 gIndex 下标的组内元素个数 同时也相当于下一个可存入元素的下标值【下标从0开始】
     * @param numCount 目前 已经枚举 数字的个数 同时也相当于要进行判断第 numCount 下标的数【下标从0开始】
     * @param start    使组合型枚举保持唯一排列顺序 将要判断枚举数的起点下标
     */
    static void dfs(int gIndex, int gCount, int numCount, int start) {
        if (gIndex >= ans) return;
        if (numCount >= n) ans = gIndex;
        // 是否开新组
        boolean flag = true;

        for (int i = start; i < n; i++) {
            if (!st[i] && check(group[gIndex], gCount,i)){
                // 可以放入当前组 不需要开新组
                flag = false;
                st[i] = true;

                // 每个组存元素存下标
                group[gIndex][gCount] = i;
                dfs(gIndex, gCount + 1, numCount + 1, i + 1);

                // 恢复现场
                st[i] = false;
            }
        }
        if (flag) dfs(gIndex + 1, 0, numCount, 0);
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String[] s1 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(s1[i]);

        dfs(1, 0, 0, 0);

        System.out.println(ans);
    }
}