补集转化，求不符合条件的三元组数目
但是怎么统计呢，这里我没想到
【如果三个数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的素因数然后容斥原理……
其实仔细观察可知，+-的的系数其实就是莫比乌斯函数，那么我们用线性筛求出莫比乌斯函数计算就好了
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 int p[100010],u[100010],v[100010],s[100010],w[100010],a[100010]; 6 int t; 7 8 int main() 9 { 10 u[1]=1; 11 for (int i=2; i<=100000; i++) 12 { 13 if (!v[i]) 14 { 15 p[++t]=i; 16 u[i]=-1; 17 } 18 for (int j=1; j<=t; j++) 19 { 20 if (i*p[j]>100000) break; 21 v[i*p[j]]=1; 22 if (i%p[j]==0) 23 { 24 u[i*p[j]]=0; 25 break; 26 } 27 else u[i*p[j]]=-u[i]; 28 } 29 } 30 int cas; 31 scanf("%d",&cas); 32 while (cas--) 33 { 34 int n,m=0; 35 scanf("%d",&n); 36 memset(v,0,sizeof(v)); 37 memset(s,0,sizeof(s)); 38 memset(w,0,sizeof(w)); 39 for (int i=1; i<=n; i++) 40 { 41 scanf("%d",&a[i]); 42 v[a[i]]++; 43 m=max(m,a[i]); 44 } 45 ll ans=0; 46 for (int i=1; i<=m; i++) 47 { 48 for (int j=i; j<=m; j+=i) s[i]+=v[j]; 49 for (int j=i; j<=m; j+=i) w[j]+=s[i]*u[i]; 50 } 51 for (int i=1; i<=n; i++) 52 if (a[i]>1) ans+=1ll*w[a[i]]*(n-w[a[i]]-1); 53 printf("%lld ",1ll*n*(n-1)*(n-2)/6-ans/2); 54 } 55 }
如果三个数a, b, c不符合条件，那么一定有一对是互质的，有一对是不互质的。不妨令a, b互质，b, c不互质。