赞
踩
蒜头君给定 n 个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?
输入格式
第一行是一个正整数 n。1≤n≤10。
第二行是 n 个不大于 10000 的正整数。
输出格式
一个正整数,即最少需要的组数。
输出时每行末尾的多余空格,不影响答案正确性
样例输入
6
14 20 33 117 143 175
样例输出
3
题目链接:https://nanti.jisuanke.com/t/T1216
解题思路:每个组开设一个数组存放,新的整数进行:1.如果与某个组的成员不影响互质性,那么就存放进这个组。 2.如果不存在1的情况,那么就另开一个组单独存放此整数。
/* 对每个数进行遍历: 1.和已有组的成员不影响互质性,就放进去 2.如果有影响,不能放入任何一个已有组,就自成一组 */ #include <iostream> #include <vector> using namespace std; int n; int digits[15]; int groupcount; vector <int> groups[15]; int gys(int a,int b){ if( b == 0 ) return a; return gys(b,a%b); } void dfs(int index){ //现在正在处理第index个数(第index还没处理) if(index == n) return ; int t=0; int flag2=0; for(int i=0;i<groupcount;i++) //遍历已有的每个组,判断互质 { int flag1=0; for(int j=0;j<groups[i].size();j++) { if(digits[index] <= groups[i][j]) t=gys(groups[i][j],digits[index]); else t=gys(digits[index],groups[i][j]); if( t !=1 ) { flag1=1; break; } } if(flag1 == 0) { flag2=1; groups[i].push_back(digits[index]); break; } } if( flag2 == 0) groups[groupcount++].push_back(digits[index]); dfs(index+1); return ; } int main(){ cin >> n ; for(int i=0;i<n;i++) { cin >> digits[i]; } dfs(0); cout << groupcount << endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。