hdu 5072両(いいえ)互质个数逆方向＋容斥

http://acm.hdu.edu.cn/showproblem.php?pid=5072
n個の異なった数(<=1 e 5)の中でどれだけの組の3元グループ(a、b、c)の2つの相互の質あるいは2つの相互の質があることを求めます.
逆方向に解いて、すべての不一致の状況を求めて、全体の状況数で減らせばいいです.
先に容斥で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;
}