题目1221分成互质组题目描述给定n个正整数将它们分组使得每组中任意两个数互质。至少要分成多少个组输入第一行是一个正整数n。1 ≤ n ≤ 10。第二行是n个不大于10000的正整数。输出一个正整数即最少需要的组数。时空限制1s / 64MB样例输入6 14 20 33 117 143 175样例输出3代码#includebits/stdc.husingnamespacestd;constintN1010;intn,p[N],group[N][N],ansN;boolvis[N];intgcd(inta,intb){if(!b)returna;returngcd(b,a%b);}boolcheck(intgroup[],intgc,inti){for(intj0;jgc;j)if(gcd(p[group[j]],p[i])1)returnfalse;returntrue;}voiddfs(intk,intgc,intpc,intst){if(kans)return;if(pcn){ansmin(ans,k);return;}boolffalse;for(intist;in;i){if(!vis[i]check(group[k],gc,i)){vis[i]true;group[k][gc]i;ftrue;dfs(k,gc1,pc1,i1);vis[i]false;ffalse;}}if(!f)dfs(k1,0,pc,0);}intmain(){cinn;for(inti0;in;i)cinp[i];dfs(1,0,0,0);coutans;return0;}结果