1221：分成互质组时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4533 通过数: 2089 【题目描述】给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？ 【输入】第一行是一个正整数n。1 ≤ n ≤ 10。 第二行是n个不大于10000的正整数。 【输出】一个正整数，即最少需要的组数。 【输入样例】6 14 20 33 117 143 175 【输出样例】3 【来源】No |
代码如下：
#include <bits/stdc++.h>
#define MAXN 10500
using namespace std;
int a[MAXN];
int cnt[MAXN];
int t;
bool ok(int x) //这里用了一个数组cnt来记录同一个组内的数可以被哪些数整除
{for(int i=2; i<x; i++){if(x%i==0){if(cnt[i]) //说明组内已有其它数可以被i整除，即x与组内的数不是互质{return false;}else{cnt[i]++;}}}return true;
}void dfs(int k,int x)
{for(int i=k; i<t; i++) //多整个数进行查找{if(ok(a[i])) //如果与组内的数互质{a[i]=-1; //说明这个数已经在别的组里了k++;dfs(k,a[k]); //注意不要进行回溯}// cout<<"a[i]="<<a[i]<<endl;}return ;
}int main()
{int i,ans=0;cin>>t;for(i=0; i<t; i++){cin>>a[i];}for(i=0; i<t; i++){if(a[i]!=-1){ans++; //每调用一次dfs，就多一个分组memset(cnt,0,sizeof(cnt)); //记得要清零dfs(i,a[i]);}}cout<<ans<<endl;return 0;
}
/*
6
14 20 33 117 143 175
*/