分成互质组——DFS

DFS"/>

分成互质组——DFS

给定 n 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

输入格式
第一行是一个正整数 n。
第二行是 n 个不大于10000的正整数。

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

数据范围
1≤n≤10

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

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
typedef pair<int,int> PII;
const int N=100;
int w[N];
bool vis[N];
int ans,n;
int g[N][N];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
bool is_primes(int a[],int n,int x)
{  for (int i=0;i<n;i++){if (gcd(w[a[i]],w[x])>1) return 0;}return 1;
}
void dfs(int u,int len,int cnt,int s)
{if (u>ans) return ;if (cnt==n) {ans=u;return ;}bool falg=0;for (int i=s;i<n;i++){if (!vis[i]&&is_primes(g[u],len,i)){vis[i]=1;g[u][len]=i;dfs(u,len+1,cnt+1,i+1);vis[i]=0;falg=1;}}if (!falg) dfs(u+1,0,cnt,0);
}
signed main()
{ios;cin>>n;for (int i=0;i<n;i++) cin>>w[i];ans=n;dfs(1,0,0,0);cout<<ans;return 0;
}