题意： 给出n个数（n<100000）, 每个数都不大于100000，数字不会有重复。现在随意抽出3个，问三个彼此互质 或者 三个彼此不互质的数目有多少。
思路： 这道题的原型是同色三角形， 可能现场很多队伍都知道这个模型， 所以这道题当时过的队伍还是挺多的。
这道题反着想，就是三个数中只有一对互质 或者只有两对互质的个数。
研究后发现 对于每个数字求出与其不互质的个数k 那么 sum ( k*(n-1-k) )/2 就是相反的数目， 所以最终的答案就是 C(n,3) - sum ( k*(n-1-k) )/2.
现在依然存在一个问题就是如何求出每个数的不互质数的个数，这个其实用容斥原理。 对于数字 a ，求出a的所有素因子， 然后枚举素因子可以构成的所有数字(构成数的过程中素因子用的个数不能超过1) w，
求出原先数组中能被w整除的个数。 如果w的素因子个数为奇数就加， 偶数就减。 这就是容斥的过程。
现在还是存在一个问题， 如何快速算出原先数组中能整出w的个数。 首先对原先数据中的每个数字a， 求出所有的素因子， 然后枚举素因子可以构成的所有数字(构成数的过程中素因子用的个数不能超过1)，
对于每一个枚举的数统计加1. 这样就能提前预处理出来。
算法的整体复杂度为 O(n*64*6);
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
const int N = 200500;
typedef long long LL;
int p[N];
int num;
bool in[N];
int a[N];
int n;
int nn[N];
void get_prime()
{
num = 0;
for(int i=2; i<N; i++)
{
if(!in[i])
{
p[num++] = i;
for(int j=i; j<N; j+=i)
{
in[j] = true;
}
}
}
}
void init()
{
memset(nn, 0, sizeof(nn));
int cnt = 0;
int ele[100];
scanf("%d", &n);
int temp = 0;
for(int i=0; i<n; i++)
{
scanf("%d", &a[i]);
temp = a[i];
cnt = 0;
for(int j=0; p[j]*p[j] <= temp; j++)
{
if(temp % p[j] == 0)
{
ele[cnt++] = p[j];
while(temp%p[j] == 0)
temp /= p[j];
}
}
if(temp != 1)
{
ele[cnt++] = temp;
}
for(int j=1; j<(1<<cnt); j++)
{
temp = 1;
for(int k=0; k<cnt; k++)
{
if( (1<<k) & j )
{
temp *= ele[k];
}
}
nn[temp]++;
}
}
}
void solve()
{
LL ans = n;
LL ss = 0;
int temp;
ans = ans*(n-1)*(n-2)/6;
for(int i=0; i<n; i++)
{
int cnt = 0;
int ele[100];
temp = a[i];
cnt = 0;
for(int j=0; p[j]*p[j] <= temp; j++)
{
if(temp % p[j] == 0)
{
ele[cnt++] = p[j];
while(temp%p[j] == 0)
temp /= p[j];
}
}
if(temp != 1)
{
ele[cnt++] = temp;
}
LL ret = 0;
for(int j=1; j<(1<<cnt); j++)
{
temp = 1;
int hh = 0;
for(int k=0; k<cnt; k++)
{
if( (1<<k) & j )
{
temp *= ele[k];
hh++;
}
}
if(hh%2 == 1) ret += nn[temp];
else ret -= nn[temp];
}
if(ret == 0) continue;
ss = ss + (ret-1)*(n-ret);
// cout<<i<<" "<<ret<<" "<<ss<<endl;
}
cout<<ans - ss/2<<endl;
}
int main()
{
get_prime();
int t;
scanf("%d", &t);
while(t--)
{
init();
solve();
}
return 0;
}