说是莫比乌斯反演，其实只是玩儿玩儿内个miu函数而已……
原题：
wty 打算攻击 applepi 的用来存放机密数据的水晶系统。 applepi 早有察觉，于是布置了一个密码系统来防备 wty 的攻击。 wty 经过研究发现，applepi 的密码系统中最关键的部分在于一 串四个正整数组成的密钥，四个正整数的顺序可以任意排列， 并且这四个正整数的最大公约数为 1。
wty 已经成功地把这四个正整数限制在了 N 个正整数构成的集合中，但是，密钥的数目 可能仍然是很庞大的。wty 希望知道有多少组可能的密钥。当然，applepi 已经挫败了 wty 的阴谋，但是他对这个问题也是饶有兴趣的。所以说，现在你需要帮助 applepi 算出有多少 组可能密钥，为 applepi 评估他的水晶系统的安全性提供参考。
N≤10000，集合中的数不大于 10000
题目要求四个数gcd为1，可以求出不为1的有几个，然后用总数减
先通过枚举数来求出共有num[i]个数含有因子i，c(num[i],4)即为gcd为i的情况个数，使用容斥去掉2*3和6这样的重复计算即可
手玩小数据可以发现，搞容斥的+或-的情况刚好和miu符合，比如2应该-，miu就是-1,6应该+，miu就是1之类的，所以就可以直接用miu来计算是过程变得更高端
核心代码：if(_num>=4) ans+=miu[k]*_num*(_num-1)*(_num-2)*(_num-3)/24;
需要注意一点，求num[i]的时候直接枚举会T，要用sqrt优化，最后根据miu求ans的时候是直接从1枚举到maxx（最大的内个数），但是求num[i]的时候不能枚举到sqrt(maxx)，而是枚举到sqrt(a[i])
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){int z=,mark=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mark=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mark;
}
int n,a[];
bool kang[]; int zhi[],ztop=;
int miu[];
int num[];
void get_miu(){
memset(kang,,sizeof(kang));
miu[]=;
for(int i=;i<=;i++){
if(!kang[i]){ zhi[++ztop]=i; miu[i]=-;}
for(int j=;zhi[j]*i<=;j++){
kang[zhi[j]*i]=true;
if(i%zhi[j]==){ miu[zhi[j]*i]=; break;}
miu[zhi[j]*i]=-miu[i];
}
}
}
int main(){//freopen("ddd.in","r",stdin);
get_miu();
while(scanf("%d",&n)!=EOF){
memset(num,,sizeof(num));
int maxx=;
for(int i=;i<=n;i++){ a[i]=read(); maxx=max(maxx,a[i]);}
if(n<){ cout<<<<endl; continue;}
for(int i=;i<=n;i++){
int smax=int(sqrt(a[i]*1.0));
for(int j=;j<=smax;j++)if(a[i]%j==){
num[j]++;
if(a[i]/j!=j) num[a[i]/j]++;
}
}
long long ans=;
for(int k=;k<=maxx;k++){
long long _num=num[k];
if(_num>=) ans+=miu[k]*_num*(_num-)*(_num-)*(_num-)/;
}
cout<<ans<<endl;
}
return ;
}