题意
选出三个数，要求两两互质或是两两不互质。求有多少组这样的三个数。
分析
同色三角形
n个点 每两个点连一条边（可以为红色或者黑色），求形成的三条边颜色相同的三角形的个数
反面考虑这个问题，只需要c(n,3)减去不同色的三角形个数即可
对于每一个点，所形成的不同色三角形即为 红色边的数量*黑色边的数量，所以可以O(n)地算出不同色三角形的个数（注意总数要除以2）
然后用c(n,3)减一下即可
对于这个题，如果把互质看作红色边，不互质看作黑色边，就可以转化为同色三角形问题了
那如何求 互质的个数和不互质的个数呢？
[可以参考一下这里]利用容斥原理求出每个数的不互质个数m，那么互质个数则为n-m-1。最终答案则为C(n,3)-m*(n-m+1)/2.
预处理每个数的质因子，计算出每种质因子搭配的个数(表明n个数中有多少个为其倍数)num[].
其他看代码:
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<math.h> #include<vector> using namespace std; #define eps 1e-12 #define inff 0x3fffffff #define nn 110000 typedef __int64 LL; int n; int a[nn]; int num[nn]; vector<int>p[nn]; bool use[nn]; void init() { memset(use,false,sizeof(use)); for(int i=2;i<=100000;i++)//分解质因子 { if(!use[i]) { for(int j=i;j<=100000;j+=i) { p[j].push_back(i); use[j]=true; } } } } int main() { int t,i,j,k; init(); scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } memset(num,0,sizeof(num)); int lv; int ix; for(i=1;i<=n;i++)//状压 { if(a[i]==1) continue; lv=p[a[i]].size(); for(j=1;j<(1<<lv);j++) { ix=1; for(k=0;k<lv;k++) { if(((1<<k)&j)) { ix*=p[a[i]][k]; } } num[ix]++;//表示n个数中为ix的倍数的个数 } } int fc; LL tem; LL ans=0; LL m=n; for(i=1;i<=n;i++) { if(a[i]==1) continue; lv=p[a[i]].size(); tem=0; for(j=1;j<(1<<lv);j++) { ix=1; fc=0; for(k=0;k<lv;k++) { if(((1<<k)&j)) { ix*=p[a[i]][k]; fc++; } } if(fc&1) { tem+=num[ix]; } else tem-=num[ix]; } //tem-1才是与其不互质的个数，意思为减去自身 ans+=(tem-1)*(m-tem); } ans/=2; ans=m*(m-1)*(m-2)/6-ans; printf("%I64d ",ans); } return 0; }