题目链接

做法非常蠢，复杂度可能不是很优，但同样可过本题。

听好多巨佬说可以用多项式做

由于每个数分解质因数后每个因数的幂次不会超过 $1$ 并且所有质因数都在 $[1,~50]$ 之间（只有 $15$ 个质数），考虑输入后直接将每个数转为 $15$ 位的二进制数，第 $i$ 位为 $1$ 表示第 $i$ 个质数是该数的一个质因子。

考虑令 $f[S]$ 表示转化后的数值为 $S$ 的子集的数的数量，令 $g[t][S]$ 表示在所有含有第 $t$ 个质因子中的，其集合去除 $t$ 后为 $S$ 子集的数的数量。

如果 $cnt[i]$ 表示转化后为 $i$ 的数的数量，$rev[S]$ 表示 $S$ 的补集，显然答案为：

$$\sum_{i=0}^{2^{15}-1} cnt[i] \times f[rev[i]] + \sum_{t=0}^{14}\sum_{i=0}^{2^{15}-1} [t \notin i] \times cnt[i] \times g[t][rev[i]]$$

式子中第一项枚举了所有两数 $\gcd$ 为 $1$ 的情况，第二项枚举了所有两数 $\gcd$ 为 $t$ 的情况，加起来即为总答案。

至于如何推出 $f,~g$ 两个 DP 数组，考虑直接枚举子集进行统计，复杂度为 $O(3^n)$。

代码

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {

// fread

}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 100005

const int prime[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

int cnt[1 << 15], f[1 << 15], g[15][1 << 15], rev[1 << 15];

void solve(void) {
    int n = read<int>(), maxS = 1 << 15;
    memset(cnt, 0, sizeof(cnt));
    for (register int i = 0; i < n; i++) {
        long long num = read<long long>();
        int stat = 0;
        for (register int j = 0; j < 15; j++)
            if (num % prime[j] == 0) stat |= 1 << j;
        cnt[stat]++;
    }
    for (register int i = 0; i < maxS; i++) {
        f[i] = cnt[0];
        for (register int j = i; j; j = (j - 1) & i) f[i] += cnt[j];
    }
    for (register int t = 0; t < 15; t++)
        for (register int i = 0; i < maxS; i++) {
            g[t][i] = cnt[1 << t];
            if (i >> t & 1) continue;
            for (register int j = i; j; j = (j - 1) & i) g[t][i] += cnt[j | (1 << t)];
        }
    long long answer = 0;
    for (register int i = 0; i < maxS; i++) answer += 1LL * cnt[i] * f[rev[i]];
    for (register int i = 0; i < 15; i++)
        for (register int j = 0; j < maxS; j++) {
            if (!(j >> i & 1)) continue;
            answer += 1LL * cnt[j] * g[i][rev[j]];
        }
    write(answer), putch('\n');
    return;
}

int main() {
    for (register int i = 0; i < (1 << 15); i++) rev[i] = (~i) & ((1 << 15) - 1);
    int _ = read<int>();
    while (_--) solve();
    return 0;
}