hdu5072-Coprime（容斥原理）

题意：给N个互不相同的数，选择出两两互质或者两两不互质的三个数，有多少种选法。

题解：一共有C(N,3)中选择方式，减去不符合要求的，剩下的就是答案。

详见 http://blog.csdn.net/csuhoward/article/details/44978087

看到有的题解说是同色三角形，感觉和CCPC长春那个六个人三个人必有互相认识或者互相不认识好像= =

开始求出了所有质数的组合，然后一直T，后来看题解发现只要对现有的数做预处理就可以=。=

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long long ll;

const int N = 100005;
int a[N], n;
int fac[N][10], sz[N];
int ret[N];
int vis[N];

int prime[N], p;
bool is_prime[N];

int sieve()
{
    for (int i = 0; i < N; ++i) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < N; ++i) {
        if (is_prime[i]) {
            prime[p++] = i;
            for (int j = 2 * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return p;
}

void init() {
    int cnt, x, limit;
    for (int i = 1; i <= 100000; ++i) {
        x = i, limit = sqrt(x), cnt = 0;
        for (int k = 0; prime[k] <= limit; ++k) {
            if (x % prime[k] == 0) fac[i][cnt++] = prime[k];
            while (x % prime[k] == 0) x /= prime[k];
        }
        if (x > 1) fac[i][cnt++] = x;
        sz[i] = cnt;
    }
}

ll solve() {
    memset(ret, 0, sizeof ret);
    for (int i = 1; i < N; ++i) {
        for (int j = i; j < N; j += i) {
            if (vis[j]) ret[i]++;
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        int cnt = sz[a[i]];
        int st = 1<<cnt;
        ll tmp = 0;
        for (int k = 1; k < st; ++k) {
            int val = 1;
            int w = 0;
            for (int j = 0; j < cnt; ++j) {
                if (k & (1<<j)) {
                    val *= fac[a[i]][j];
                    w ^= 1;
                }
            }
            if (w) tmp += ret[val]-1;
            else tmp -= ret[val]-1;
        }
        ans += tmp * (n-tmp-1);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    sieve();
    init();
    while (T--) {
        scanf("%d", &n);
        memset(vis, 0, sizeof vis); // everyone has unique id
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]), vis[a[i]] = 1;
        ll ans = solve();
        ll tot = (ll)n * (n-1) * (n-2) / 6;
        printf("%lld
", tot - ans/2);
    }
    return 0;
}