题意
选出三个数，要求两两互质或是两两不互质。求有多少组这样的三个数。
分析
同色三角形
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=;i<=;i++)//分解质因子
{
if(!use[i])
{
for(int j=i;j<=;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=;i<=n;i++)
{
scanf("%d",&a[i]);
}
memset(num,,sizeof(num));
int lv;
int ix;
for(i=;i<=n;i++)//状压
{
if(a[i]==)
continue;
lv=p[a[i]].size();
for(j=;j<(<<lv);j++)
{
ix=;
for(k=;k<lv;k++)
{
if(((<<k)&j))
{
ix*=p[a[i]][k];
}
}
num[ix]++;//表示n个数中为ix的倍数的个数
}
}
int fc;
LL tem;
LL ans=;
LL m=n;
for(i=;i<=n;i++)
{
if(a[i]==)
continue;
lv=p[a[i]].size();
tem=;
for(j=;j<(<<lv);j++)
{
ix=;
fc=;
for(k=;k<lv;k++)
{
if(((<<k)&j))
{
ix*=p[a[i]][k];
fc++;
}
}
if(fc&)
{
tem+=num[ix];
}
else
tem-=num[ix];
}
//tem-1才是与其不互质的个数，意思为减去自身
ans+=(tem-)*(m-tem);
}
ans/=;
ans=m*(m-)*(m-)/-ans;
printf("%I64d\n",ans);
}
return ;
}