给出n个数，求选出4个数组合，使其gcd为1，,(n<=10000),每个数(<=10000)。
解
理解1：容斥原理
注意到Mobius反演式子不好写出，于是我们考虑它的兄弟，容斥，于是设(F(d))表示数中有约数d的个数，所以由容斥原理，我们不难得到
[ans=sum_{d=1}^{10000}F(d)mu(d)
]
预处理出函数(mu),和(F),代入式子枚举即可。
理解2:Mobius反演
考虑到无法写出具体的式子，于是我们可以列出抽象式子，设(f(d))为选出4个数gcd为d的个数，设(F(d))表示为选出4个数公约数为d的方案数，所以由Mobius反演定理，我们有
[f(d)=sum_{d|x}F(x)mu(x/d)
]
所以
[ans=f(1)sum_{x=1}^{10000}F(x)mu(x)
]
代入式子枚举即可。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define ll long long
using namespace std;
ll rc[10001];
bool check[10001];
int prime[2001],pt,mu[10001];
il ll C4(ll);
il void prepare(int);
int main(){
int n,i,j;prepare(10000);ll ans;
while(scanf("%d",&n)!=EOF){
ans&=0,memset(rc,0,sizeof(rc));
while(n--){
scanf("%d",&i);
for(j=1;j*j<i;++j)
if(!(i%j))++rc[j],++rc[i/j];
if(j*j==i)++rc[j];
}for(i=1;i<=10000;++i)ans+=mu[i]*C4(rc[i]);
printf("%lld
",ans);
}
return 0;
}
il ll C4(ll n){
return n*(n-1)*(n-2)*(n-3)/24;
}
il void prepare(int n){
int i,j;mu[1]=1;
for(i=2;i<=n;++i){
if(!check[i])prime[++pt]=i,mu[i]=-1;
for(j=1;j<=pt&&prime[j]*i<=n;++j){
check[i*prime[j]]|=true;
if(!(i%prime[j]))break;
mu[i*prime[j]]=~mu[i]+1;
}
}
}