给出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 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define ll long longusing 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