2023.10.6 闲话

T1

转化为 $\gcd(x_1,x_2,\cdots,x_k)=i$。但是还是不好做，继续转化为 $i\mid\gcd(x_1,x_2,\cdots,x_k)$。从而要求 $i\mid x_j$。

对于每个 $i$ 统计其倍数的数量。倒着容斥答案即可。

时间复杂度 $\mathcal{O}(m\log m)$。

for (int i = m; i >= 1; i--) {
    int w = 0;
    for (int j = i; j <= m; j += i) w += cnt[j];
    f[i] = Pow(w, k);
    for (int j = 2 * i; j <= m; j += i)
        f[i] = ((f[i] - f[j]) % mod + mod) % mod;
}

T2

Trie 启发式合并。由于 01-Trie 也只有两个儿子，所以合并过程和线段树合并很类似。

关于点权的处理，可以先离线，把最后树森林的形态建出来。对每个点跑其到根路径的异或和作为点权，由于异或的性质，容易说明后续操作可以直接用这个点权。

关于启发式。将小的连通块插到大的连通块里即可。

时间复杂度 $\mathcal{O}(n\log n\log W)$。

struct Trie {
    int ch[MAXN * 32][2], sz;

    int insert(int x, int d) {
        if (d == -1) return ++sz;
        int u = ++sz;
        int c = x >> d & 1;
        ch[u][c] = insert(x, d - 1);
        return u;
    }

    int query(int u, int x, int d) {
        if (d == -1) return 0;
        int c = x >> d & 1;
        if (ch[u][c ^ 1]) return (1 << d) | query(ch[u][c ^ 1], x, d - 1);
        return query(ch[u][c], x, d - 1);
    }

    int merge(int u, int v) {
        if (!u || !v) return u + v;
        ch[u][0] = merge(ch[u][0], ch[v][0]);
        ch[u][1] = merge(ch[u][1], ch[v][1]);
        return u;
    }
} T;

if (opt == 1) {
    u = find(u), v = find(v);
    if (comp[u].size() < comp[v].size()) swap(u, v);
    un(u, v);
    rt[u] = T.merge(rt[u], rt[v]);
    for (int x: comp[v]) {
        ans[u] = max(ans[u], T.query(rt[u], a[x], 30));
        comp[u].push_back(x);
    }
} else {
    u = find(u);
    printf("%d\n", ans[u]);
}