题意:

给定很多个数 (100000 以内个 100000 以内的数), 求选出三个数使其要么两两互质，要么两两不互质，的方案数。

分析:

如果用一条红边连接互质的数，黑边连接不互质的数。那么我们就要求单色三角形的数目。这样的问题往往可以通过补集转化转化为求双色三角形的数目，再用三角形总数减去双色三角形数目得到答案。现在我们发现在 1E5 的数据范围内你没办法枚举每个三角形，甚至连每一条边的时间都是不够的。

所以我们可以考虑枚举每个三角形的某个顶点，再看它连出的黑边数 a 和红边数 b，那么以它为一个顶点的双色三角形数就是 (a*b)。那么所有双色三角形数就是 (每个三角形枚举了两次)

$$\frac{1}{2}\sum{a_ib_i}$$

那么现在问题转化为了: 如何高效地求每个点连出的红边和黑边数。也就是说如何快速获得与每个数互质与不互质的数的个数。

我们发现求与一个数不互质的数的个数是更方便的。所以拿 n 减去不互质的数的个数再减１就是互质的数的个数。

现在一个恶心的问题已经转化为了很简单的问题：如何快速求与每个数不互质的数的个数。

解决:

先证明一个引理:1E5 以内的数至多有６个质因子。因为 2×3×5×7×13×17×19>1E5。那么我们只需要知道每个数的质因子，以及有多少数拥有特定的因子。那么我们可以用容斥原理在 64n 的时间复杂度内求出这个问题的答案。这件事我们可以在 O(nlnn) 内预处理出。那么这件事就解决了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 100000

using namespace std;

char mp[MX+1];
int yinz[MX+1][10],ynum[MX+1];
int snum[MX+1];
int n,src[MX+1];

void init()
{
    for(int i=2;i<=MX;)
    {
        for(int j=1;j*i<=MX;j++)
        {
            ynum[j*i]++;
            yinz[j*i][ynum[j*i]]=i;
            mp[j*i]=1;
        }
        while(mp[i])i++;
    }
}

int ans;
void sch(int pos,int num,int have,int x)
{
    if(pos==ynum[x]+1)
    {
        if(have==0)return;
        if(have%2)ans+=snum[num];
        else ans-=snum[num];
        return;
    }
    sch(pos+1,num,have,x);
    sch(pos+1,num*yinz[x][pos],have+1,x);
}

void dfs(int pos,int num,int have,int x)
{
    if(pos==ynum[x]+1)
    {
        if(have==0)return;
        snum[num]++;
        return;
    }
    dfs(pos+1,num,have,x);
    dfs(pos+1,num*yinz[x][pos],have+1,x);
}

void inpt()
{
    memset(snum,0,sizeof(snum));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&src[i]);
        dfs(1,1,0,src[i]);
    }
}

void work()
{
    long long tot=0;
    for(int i=1;i<=n;i++)
    {
        if(src[i]==1)continue;
        ans=-1;
        sch(1,1,0,src[i]);
        tot+=(long long)ans*((long long)n-(long long)ans-1);
    }
    cout<<(long long)n*(long long)((long long)n-1)*(long long)((long long)n-2)/6-(long long)tot/2<<endl;
}

int main()
{
    int t;
    init();
    scanf("%d",&t);
    for(int w=1;w<=t;w++)
    {
        inpt();
        work();
    }
    return 0;
}