You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

2.4 KiB

This file contains invisible Unicode characters!

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

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;
}