简答题 偏难
#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 &lt;algorithm&gt; #include &lt;bits/stdc++.h&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iomanip&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;string&gt; 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 &gt; n) {     ans = min(group_cnt, ans);     return;   }   for (int i = 1; i &lt;= group_cnt; i++) {     int pd = 0;     for (int j = 1; j &lt;= 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", &amp;n);   for (int i = 1; i &lt;= n; i++)     scanf("%d", &amp;a[i]);   for (int i = 1; i &lt;= n; i++)     for (int j = 1; j &lt;= n; j++) {       if (hz(a[i], a[j]) == 1) {         huzhi[i][j] = 1;       }     }   ans = 10;   ss(1, 0);   printf("%d", ans);   return 0; }</pre>
这道题暂未补解析。