hdu 5072 Coprime(數論)

hdu 5072 Coprime(數論)

題目鏈接：hdu 5072 Coprime

題目大意：給定N個數，問能選出多少個3元組，要麼[(a, b) = (b, c) = (a, c) = 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠

1]。

解題思路：這題可以換個角度想，可以將三個數看做三角形的三條邊，互質即邊的顏色為1，否則為0，那麼要求的即為

三條邊顏色相同的三角形有多少個。

總的三角形的個數可求，那麼如果求出三條邊不完全相同的三角形個數，相減一下即可。

枚舉頂點，然後確定以該點形成的三角會形成多少個不滿足三角形，即在1中選一條，0中選一條。這樣的話一個不滿足

三角形會被計算2次，ans / 2即可。

那麼問題轉換成求每個數互質或者不互質的數有多少個，將每個數差分質因子，統計每個包含質因子x的數有多少個，

最用計算每個數的時候，用容斥原理計算即可。

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 1e5;

int np, pri[maxn + 5], vis[maxn + 5];
int k, fac[maxn + 5];

int v[maxn + 5];
vector g[maxn + 5];

void prime_table(int n) {
    np = 0;
    for (int i = 2; i <= n; i++) {
        if (vis[i])
            continue;
        pri[np++] = i;
        for (int j = i * 2; j <= n; j += i)
            vis[j] = 1;
    }
}

void div_fac(int n, int& cnt) {
    cnt = 0;
    for (int i = 0; i < np && pri[i] * pri[i] <= n; i++) {
        if (n % pri[i] == 0) {
            fac[cnt++] = pri[i];
            while (n % pri[i] == 0)
                n /= pri[i];
        }
    }
    if (n != 1)
        fac[cnt++] = n;
}

void dfs (int u, int d, int idx) {
    if (d >= v[idx]) {
        if (u != 1)
            g[idx].push_back(u);
        return;
    }

    dfs(u, d + 1, idx);
    dfs(u * fac[d], d + 1, idx);
}

void init () {
    np = 0;
    memset(vis, 0, sizeof(vis));
    prime_table(maxn);

    for (int i = 2; i <= maxn; i++) {
        div_fac(i, v[i]);
        dfs(1, 0, i);
    }
}

int N, f[maxn + 5], c[maxn + 5];

void input () {
    int x;
    scanf("%d", &N);
    memset(c, 0, sizeof(c));
    memset(f, 0, sizeof(f));

    for (int i = 0; i < N; i++) {
        scanf("%d", &x);
        c[x]++;
    }
    for (int i = 2; i <= maxn; i++) {
        if (c[i] == 0)
            continue;
        for (int j = 0; j < g[i].size(); j++)
            f[g[i][j]] += c[i];
    }
}

typedef long long ll;

int count (int n) {
    int ret = 0;
    for (int i = 0; i < g[n].size(); i++) {
        int k = g[n][i];
        if (v[k]&1)
            ret += (f[k] - 1);
        else
            ret -= (f[k] - 1);
    }
    return ret;
}

ll solve () {
    ll ret = 0;
    for (int i = 2; i <= maxn; i++) {
        if (c[i] == 0)
            continue;
        ll k = count(i);
        ret += k * (N - 1 - k);
    }
    ll a = N;
    ll sum = 1LL * a * (a - 1) * (a - 2) / 6;
    return sum - ret / 2;
}

int main () {
    init();
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        input();
        printf("%I64d\n", solve());
    }
    return 0;
}