分成互质组

题目

时间限制: 1000 ms ? ? ? ? 内存限制: 65536 KB
提交数: 4533 ? ? 通过数: 2089
【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

【输入】
第一行是一个正整数n。1 ≤ n ≤ 10。

第二行是n个不大于10000的正整数。

【输出】
一个正整数，即最少需要的组数。

【输入样例】
6
14 20 33 117 143 175
【输出样例】
3

思路

将每个数依次放入

每次遍历当前有的所有组

挨个判断是否可以放入这个组

如果可以放入，则分放与不放两次递归

注意：一定要记得单独一组的情况

如何判断是否可以放入当前组：

遍历当前组内每个数

判断这个数是否与放入数互质

如果有一个不互质

则不可放入

（判断互质用辗转相除法最好）

代码

最后附上代码

#include<bits/stdc++.h>
using namespace std;
int a[15],n,ans,cnt=0;
int f[15][15],cntf[15];
bool pd(int a,int b)
{
?? ?int t=min(a,b);
?? ?for(int i=2;i<=t;i++)
?? ?{
?? ??? ?if(a%i==0&&b%i==0)
?? ??? ?{
?? ??? ??? ?return true;
?? ??? ?}
?? ?}
?? ?return false;
}
void dg(int t)
{
?? ?if(t==n)
?? ?{
?? ??? ?ans=min(ans,cnt);
?? ??? ?
?? ??? ?return ;
?? ?}
?? ?for(int i=1;i<=cnt;i++)
?? ?{
?? ??? ?int j;
?? ??? ?for(j=1;j<=cntf[i];j++)
?? ??? ?{
?? ??? ??? ?if(pd(a[t+1],f[i][j]))?? ?break;?? ?
?? ??? ?}
?? ??? ?if(j>cntf[i])
?? ??? ?{
?? ??? ??? ?f[i][++cntf[i]]=a[t+1];
?? ??? ??? ?dg(t+1);
?? ??? ??? ?cntf[i]--;
?? ??? ?}
?? ?}
?? ?cnt++;
?? ?if(cnt>=ans)?
?? ?{
?? ??? ?cnt--;
?? ??? ?return ;
?? ?}
?? ?cntf[cnt]++;
?? ?f[cnt][cntf[cnt]]=a[t+1];
?? ?dg(t+1);
?? ?cntf[cnt]--;
?? ?cnt--;
?? ?return ;
}
int main()
{
?? ?cin>>n;
?? ?ans=n;
?? ?for(int i=1;i<=n;i++)
?? ?{
?? ??? ?cin>>a[i];
?? ?}
?? ?dg(0);
?? ?cout<<ans;
??? ?return 0;
}