1221：分成互质组
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
【输入】
第一行是一个正整数n。1 ≤ n ≤ 10。
第二行是n个不大于10000的正整数。
【输出】
一个正整数，即最少需要的组数。
【输入样例】
6
14 20 33 117 143 175
【输出样例】
3
【来源】
No
互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。
1. #include<bits/stdc++.h> 2. using namespace std; 3. int n,a[21],cnt=99999; 4. long long b[21]; 5. long long gcd(long long a,long long b)//求最大公约数 6. { 7. if(b==0) return a; 8. return gcd(b,a%b); 9. } 10. void dfs(int k,int step) 11. { 12. if(step==n+1){//更新最优方案 13. if(k<cnt) cnt=k; 14. return; 15. } 16. for(int i=1;i<=k;i++){ 17. if(gcd(b[i],a[step])==1){ 18. b[i]*=a[step]; 19. dfs(k,step+1); 20. b[i]/=a[step]; 21. } 22. b[k+1]*=a[step]; 23. dfs(k+1,step+1); 24. b[k+1]/=a[step]; 25. } 26. } 27. int main() 28. { 29. scanf("%d",&n); 30. for(int i=1;i<=n;i++){ 31. cin>>a[i]; 32. b[i]=1; 33. } 34. sort(a+1,a+1+n); //从小到大排序 35. dfs(1,1); 36. printf("%d",cnt); 37. return 0; 38. }
