简答题
偏难
#7057
分成互质组 给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组? 时间限制:1000 内存限制:65536 输入 第一行是一个正整数n。1…
分成互质组
给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?
时间限制:1000
内存限制:65536
输入
第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。
输出
一个正整数,即最少需要的组数。
样例输入
6 14 20 33 117 143 175
样例输出
3
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int n, a[12], ans, huzhi[12][12];
int group[12][12], group_size[12];
int hz(int x, int y) {
if (y == 0)
return x;
return hz(y, x % y);
}
void ss(int x, int group_cnt) {
if (x > n) {
ans = min(group_cnt, ans);
return;
}
for (int i = 1; i <= group_cnt; i++) {
int pd = 0;
for (int j = 1; j <= group_size[i]; j++) {
if (huzhi[x][group[i][j]] == 0) {
pd = 1;
break;
}
}
if (pd == 1)
continue;
group_size[i]++;
group[i][group_size[i]] = x;
ss(x + 1, group_cnt);
group[i][group_size[i]] = 0;
group_size[i]--;
}
group_size[group_cnt + 1] = 1;
group[group_cnt + 1][1] = x;
ss(x + 1, group_cnt + 1);
group[group_cnt + 1][1] = 0;
group_size[group_cnt + 1] = 0;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (hz(a[i], a[j]) == 1) {
huzhi[i][j] = 1;
}
}
ans = 10;
ss(1, 0);
printf("%d", ans);
return 0;
}</pre>
这道题暂未补解析。