分成互质组

链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1221

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

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

【输入】

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

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

 

【输出】

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

【输入样例】

614 20 33 117 143 175

【输出样例】

3 题解：一组中的数两两互质，则任意一个数与其中两数的积互质

#include
      
       #include
       
        #include
        
         using namespace std;long long f[11];int n,minn=10,a[11];long long gcd(long long a,long long b){    if(!b)return a;    return gcd(b,a%b);}void s(int i,int k){    if(i==n+1)    {        if(k
         
          >n;    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<11;i++)f[i]=1;    s(1,1);    cout<
          
           <