一本通-1221：分成互质组（思路巧妙地DFS）

【题目描述】 给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

【输入】 第一行是一个正整数n。1 ≤ n ≤ 10。

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

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

【输入样例】 6 14 20 33 117 143 175

【输出样例】 3

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n;
vector<long long> num(15);
int res = INT_MAX;
vector<long long> used(10, 1);

long long GCD(long long a, long long b)
{
    return b == 0 ? a : GCD(b, a % b);
}

//k代表当前组数的下标
void DFS(int k, int step)
{
    if (step == n) {
        res = min(res, k + 1);
        return;
    }
    //检验前k个组能否加入step对应的数字
    for (int i = 0; i <= k; ++i) {
        if (GCD(used[i], num[step]) == 1) {
            used[i] *= num[step];
            DFS(k, step + 1);
            used[i] /= num[step];
        }
    }
    //如果前面的k个组都无法加入
    used[k + 1] *= num[step];
    DFS(k + 1, step + 1);
    used[k + 1] /= num[step];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    DFS(0, 0);
    cout << res << endl;

    return 0;
}

最初是想用一个bool类型的数组来记录哪个数字有没有使用。其实还可以很灵活的去DFS。注意要使用long long类型，否则会溢出。用k代表已经分好组的下标，依次检验step对应的数字是否可以加入前面的组，如果无法加入，k的值就增加1.