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 
     
       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
      
       =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