hdu 5072 两两(不)互质个数逆向+容斥

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\n",(LL)n*(n-1)*(n-2)/6 - sub/2);

    }

    return 0;

}