很经典的一道容斥原理问题。
设$k|gcd(a,b,c,d)$,则说明$k$均为$a,b,c,d$的约数,因此转化一下题意,也就是
容斥原理($k=1$(的倍数)的情况-$k=2$(的倍数)的情况-$k=3$(的倍数)的情况+$k=6$(的倍数)的情况$\cdots$)。

因此只需要求出约数$k$出现的次数$t$就好了,方案数即为$C_{t}^{4}$。

(不懂的话去看看算法进阶上Zap上的讲述)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long 
#define gc getchar()
using namespace std;
const int N=1e4+5;
const int M=101;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int prime[M],m;bool v[M];
void gp()
{
    for(int i=2;i<=100;i++)
    {
        if(!v[i])prime[++m]=i;
        for(int j=1;j<=m&&i*prime[j]<=100;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int num[N],a[N],p[M],sz;
void ins(int x)
{
    sz=0;
    for(int i=1;i<=m&&prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0)
        {
            p[++sz]=prime[i];
            while(x%p[sz]==0)x/=p[sz];
        }
    if(x>1)p[++sz]=x;
    for(int i=1;i<(1<<sz);i++)
    {
        int t=1,cnt=0;
        for(int k=sz-1;~k;k--)if(i>>k&1)
        {
            t*=p[k+1];++cnt;
        }
        ++a[t];if(!num[t])num[t]=cnt;
    }
}
ll c[N];
int main()
{
    gp();for(int i=4;i<=10000;i++)c[i]=1ll*i*(i-1)*(i-2)*(i-3)/24;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));int mx=0;
        for(int i=1,x;i<=n;i++)qr(x),ins(x),mx=max(x,mx);
        ll ans=0;
        for(int i=1;i<=mx;i++)if(a[i]>3)
        {
            if(num[i]&1)ans+=c[a[i]];
            else ans-=c[a[i]];
        }
        qw(c[n]-ans);puts("");
    }
    return 0;
}