http://acm.hdu.edu.cn/showproblem.php?pid=5072
求n个不同的数(<=1e5)中有多少组三元组(a, b, c)两两不互质或者两两互质。
逆向求解，把所有不符合的情况求出来用总的情况数减去即可；
先用容斥求出和a[i] 互质的个数num ，然后不符合条件的 就是 num*(n-1-num);
求法见http://blog.csdn.net/u012774187/article/details/40399567
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
const int maxn = 1e5+5;
int n,p[maxn],cnt[maxn];// 公约数计数
vector<int> q;
int main() {
int _;RD(_);while(_--){
RD(n);
for(int i = 1;i <= n;++i)
RD(p[i]);
clr0(cnt);
for(int i = 1;i <= n;++i){
for(int j = 1;j * j <= p[i];++j)if(p[i]%j == 0){
cnt[j]++;
if(p[i]/j != j)
cnt[p[i]/j]++;
}
}
LL sub = 0;
for(int i = 1;i <= n;++i){
q.clear();
int m = p[i];
for(int j = 2;j * j <= m;++j)if(m%j == 0){
q.push_back(j);
while(m%j == 0)
m/=j;
}
if(m != 1)
q.push_back(m);
int len = q.size();
LL sum = 0;
for(int j = 1;j < (1<<len);++j){
int cnt_fac = 0,u = 1;
for(int k = 0;k < len;++k)if(j & (1<<k)){
cnt_fac++;
u *= q[k];
}
if(cnt_fac & 1) sum += cnt[u];
else sum -= cnt[u];
}
if(sum) sum--;
sub += sum*(n - sum - 1);
}
printf("%I64d
",(LL)n*(n-1)*(n-2)/6 - sub/2);
}
return 0;
}