2019-03-12 分成互质组

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

typedef long long LL;
LL a[11];
int n,vis[11],Min;
LL gcd(LL a,LL b)
{
    if(a<b) return gcd(b,a);
    return a%b==0?b:gcd(b,a%b); 
}
int main(void)
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            Min++;
            for(int j=n;j>=i+1;j--)
            {
                if(!vis[j]&&gcd(a[i],a[j])==1)
                {
                    a[i]*=a[j];
                    vis[j]=1;
                } 
            }   
        }   
    }
    cout<<Min;
    return 0;
}