题意：给一些数，求在这些数中找出四个数互质的方案数。
莫比乌斯反演的式子有两种形式http://blog.csdn.net/outer_form/article/details/50588307
这里用的是第二种形式。
求出四个数的公约数为x的倍数的方案数，即可得到，四个数的公约数为x的方案数。
这里x为1。
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=10010; 9 const long long modn=1000000007; 10 int n; 11 int a[maxn*10]={}; 12 long long cnt[maxn]={},f[maxn]={}; 13 long long mic[maxn]={},su[maxn]={},tot=0; 14 bool vis[maxn]={}; 15 int main(){ 16 mic[1]=1; 17 for(int i=2;i<=maxn;i++){ 18 if(!vis[i]){ 19 su[++tot]=i; 20 mic[i]=-1; 21 } 22 for(int j=1;j<=tot;j++){ 23 int k=i*su[j]; 24 if(k>maxn)break; 25 vis[k]=1; 26 if(i%su[j])mic[k]=-mic[i]; 27 else break; 28 } 29 } 30 while(~scanf("%d",&n)){ 31 int ma=0;memset(cnt,0,sizeof(cnt)); 32 for(int i=1;i<=n;i++){ 33 scanf("%d",&a[i]); 34 ma=max(a[i],ma); 35 int w=sqrt(double(a[i])); 36 for(int j=1;j<=w;j++){ 37 if(a[i]%j==0){cnt[j]+=1;cnt[a[i]/j]+=1;} 38 } 39 if(w*w==a[i])cnt[w]--; 40 } 41 long long ans=0; 42 for(int i=1;i<=ma;i++){ 43 if(cnt[i]<4||mic[i]==0)continue; 44 ans+=mic[i]*cnt[i]*(cnt[i]-1)*(cnt[i]-2)*(cnt[i]-3)/24; 45 } 46 printf("%I64d ",ans); 47 } 48 }