7834:分成互质组
http://noi.openjudge.cn/math/7834/
总时间限制: 1000ms 内存限制: 65536kB
描述
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
输入
第一行是一个正整数n。1 <= n <= 10。
第二行是n个不大于10000的正整数。
输出
一个正整数，即最少需要的组数。
样例输入
6
14 20 33 117 143 175
样例输出
3
来源
2008年第十三届“华罗庚金杯”少年数学邀请赛 决赛第5题
1 #include <stdio.h> 2 3 int n,a[15]; 4 int f[15];//f[i]==x表示a[i]分到第x组 5 int total;//记录不同的方案数目 6 7 void fun(int i);//判断第i个数分到哪一个组 8 int gcd(int a,int b) 9 { return a%b==0?b:gcd(b,a%b); } 10 int main(int argc, char *argv[]) 11 { 12 int i; 13 scanf("%d",&n); 14 for(i=0;i<n;i++) 15 { 16 scanf("%d",&a[i]); 17 f[i]=0;//f[i]=0表示a[i]未分组 18 } 19 f[0]=1;//a[0] 分到第一组 20 total=1;//至少会有一个分组 21 fun(1); 22 printf("%d\n",total); 23 return 0; 24 } 25 void fun(int i)//判断a[i]分到哪一个组 26 { 27 int t,j,k,flag; 28 int ff[15]={0};//ff[i]==1 29 30 if(i==n) return; 31 else 32 { 33 t=a[i]; 34 for(j=i-1;j>=0;j--) 35 { 36 if(ff[j]==0)//表示a[j] 所在分组未曾检验过，那就要检验该分组 37 { 38 flag=1; 39 for(k=j;k>=0;k--)//扫描寻找a[j]所在分组的所有元素 40 { 41 if(f[k]==f[j])//若a[k]和a[j]同一个分组 42 { 43 ff[k]=1; 44 if(gcd(a[k],t)!=1) flag=0;//a[k]和a[i]不互质 45 } 46 } 47 if(flag==1) { f[i]=f[j]; break; }//a[i]和a[j]所在组的所有元素都互质，可以加入a[j]所在组 48 } 49 } 50 if(f[i]==0) f[i]=++total;//假如扫描先前所有组，都不能够把a[i]加进去，那a[i]自己形成一个新的组 51 if(i<n) fun(i+1);//寻找下一个元素的分组 52 else return ; 53 } 54 }
