首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7274

分成互质组 给定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;">// 参考答案1: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int N = 15; int n, cnt, ans = N, p[N]; vector&lt;int&gt; s[N]; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } bool check(int k, int x) {   for (int i = 0; i &lt; s[k].size(); i++)     if (gcd(s[k][i], x) &gt; 1)       return false;   return true; } void dfs(int u) {   if (u == n) {     ans = min(ans, cnt);     return;   }   for (int i = 0; i &lt; cnt; i++)     if (check(i, p[u])) {       s[i].push_back(p[u]);       dfs(u + 1);       s[i].pop_back();     }   s[cnt++].push_back(p[u]);   dfs(u + 1);   s[--cnt].pop_back(); } int main() {   cin &gt;&gt; n;   for (int i = 0; i &lt; n; i++)     cin &gt;&gt; p[i];   dfs(0);   cout &lt;&lt; ans &lt;&lt; endl;   return 0; }</pre><p><span>  </span><br/></p><pre class="brush:cpp;toolbar:false">// 参考答案2: #include &lt;iostream&gt; using namespace std; const int N = 15; int n; int p[N]; int group[N][N]; bool used[N]; int ans = N; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } bool check(int group[], int k, int x) {   for (int i = 0; i &lt; k; i++)     if (gcd(p[group[i]], x) &gt; 1)       return false;   return true; } void dfs(int g, int gc, int cnt, int start) {   if (g &gt;= ans)     return;   if (cnt == n)     ans = g;   bool flag = false;   for (int i = start; i &lt; n; i++)     if (!used[i] &amp;&amp; check(group[g], gc, p[i])) {       used[i] = true;       group[g][gc] = i;       dfs(g, gc + 1, cnt + 1, i + 1);       used[i] = false;       flag = true;     }   if (!flag)     dfs(g + 1, 0, cnt, 0); } int main() {   cin &gt;&gt; n;   for (int i = 0; i &lt; n; i++)     cin &gt;&gt; p[i];   dfs(1, 0, 0, 0);   cout &lt;&lt; ans &lt;&lt; endl;   return 0; }</pre><p><br/><span></span></p>
这道题暂未补解析。