网站引导插件,北京网站建设一条龙,网站制作最新技术,北京朝阳区二手房出售给定 n 个正整数#xff0c;将它们分组#xff0c;使得每组中任意两个数互质。至少要分成多少个组#xff1f;
输入格式 第一行是一个正整数 n。 第二行是 n 个不大于10000的正整数。
输出格式 一个正整数#xff0c;即最少需要的组数。
数据范围 1≤n≤10
输入样例将它们分组使得每组中任意两个数互质。至少要分成多少个组
输入格式 第一行是一个正整数 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 pairint,int PII;
const int N100;
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 i0;in;i){if (gcd(w[a[i]],w[x])1) return 0;}return 1;
}
void dfs(int u,int len,int cnt,int s)
{if (uans) return ;if (cntn) {ansu;return ;}bool falg0;for (int is;in;i){if (!vis[i]is_primes(g[u],len,i)){vis[i]1;g[u][len]i;dfs(u,len1,cnt1,i1);vis[i]0;falg1;}}if (!falg) dfs(u1,0,cnt,0);
}
signed main()
{ios;cinn;for (int i0;in;i) cinw[i];ansn;dfs(1,0,0,0);coutans;return 0;
}
