hdu5072

补集转化，求不符合条件的三元组数目

但是怎么统计呢，这里我没想到

【如果三个数a, b, c不符合条件，那么一定有一对是互质的，有一对是不互质的。不妨令a, b互质，b, c不互质。于是我们可以枚举b来统计答案。在除了b自己的所有数中，要么与b互质，要么与b不互质。假设n个数中有k个与b不互质的数，那么b对答案的贡献就是k*(n-k-1)。】

注意这里的求出答案之后要除以2，这是因为如果a, c互质，那么可以交换b, c的位置；如果a,c不互质，那么可以交换a, b的位置，每个答案都被计算了两遍。

那么下面就是怎么求出n个数中与x互质的数，这里可以用容斥原理解决

首先统计出在n个数中，以i为因子的数有多少个

那么与x互质的数=以1为因子-以2为因子-以3为因子+以6为因子……（假设x有因子2，3）

就是穷举x的素因数然后容斥原理……

其实仔细观察可知，+-的的系数其实就是莫比乌斯函数，那么我们用线性筛求出莫比乌斯函数计算就好了

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int p[],u[],v[],s[],w[],a[];

 int t;

 int main()

 {

     u[]=;

     for (int i=; i<=; i++)

     {

         if (!v[i])

         {

             p[++t]=i;

             u[i]=-;

         }

         for (int j=; j<=t; j++)

         {

             if (i*p[j]>) break;

             v[i*p[j]]=;

             if (i%p[j]==)

             {

                 u[i*p[j]]=;

                 break;

             }

             else u[i*p[j]]=-u[i];

         }

     }

     int cas;

     scanf("%d",&cas);

     while (cas--)

     {

         int n,m=;

         scanf("%d",&n);

         memset(v,,sizeof(v));

         memset(s,,sizeof(s));

         memset(w,,sizeof(w));

         for (int i=; i<=n; i++)

         {

             scanf("%d",&a[i]);

             v[a[i]]++;

             m=max(m,a[i]);

         }

         ll ans=;

         for (int i=; i<=m; i++)

         {

             for (int j=i; j<=m; j+=i) s[i]+=v[j];

             for (int j=i; j<=m; j+=i) w[j]+=s[i]*u[i];

         }

         for (int i=; i<=n; i++)

             if (a[i]>) ans+=1ll*w[a[i]]*(n-w[a[i]]-);

         printf("%lld\n",1ll*n*(n-)*(n-)/-ans/);

     }

 }

如果三个数a, b, c不符合条件，那么一定有一对是互质的，有一对是不互质的。不妨令a, b互质，b, c不互质。