总时间限制: 

1000ms

内存限制: 

65536kB

描述

给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

输入

第一行是一个正整数n。1 <= n <= 10。

第二行是n个不大于10000的正整数。

输出

一个正整数，即最少需要的组数。

样例输入

614 20 33 117 143 175

样例输出

3

来源

2008年第十三届“华罗庚金杯”少年数学邀请赛 决赛第5题

1 #include
       
         2 using namespace std; 3 int N,x,y; 4 int a[100]; 5 int fa[100]; 6 bool vis[100]; 7 inline int gcd(int a,int b){ 8     if(b==0) return a; 9     else return gcd(b,a%b);10 }11 inline int getfa(int x){12     if(x!=fa[x]) fa[x]=getfa(fa[x]);13     return fa[x];14 }15 inline bool jud(int x,int y){16     int root=getfa(x);17     for(int i=1;i<=N;i++){18         if(i!=y&&getfa(i)==root){19             if(gcd(a[i],a[y])==1) continue;20             else return  false;21         }22     }23     return true;24 }25 int cnt;26 int main(){27     cin>>N;28     for(int i=1;i<=N;i++) cin>>a[i],fa[i]=i;29     vis[1]=true;30     for(int i=1;i<=N;i++){31         for(int j=1;j<=N;j++){32             if(j!=i&&vis[j]==false){33                 if(jud(i,j)==true){34                     fa[j]=getfa(i);35                     vis[j]=true;36                 }37             }38         }39         40     }41     for(int i=1;i<=N;i++){42         if(fa[i]==i){43             cnt++;44         }45     }46     cout<