牛牛的最大兴趣组

形式化题目

给定 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 。选出一个尽量大的下标子集 $S$ ，使得对任意两个不同的 $i, j \in S$ ，乘积 $a_i a_j$ 不是完全立方数。求 $|S|$ 的最大值。

题面中的「乘积开三次方根是正整数」就是乘积为完全立方数，此时两人性格不合。例如 $2 \times 4 = 8 = 2^3$ ，故性格值 2 与 4 不合；而 $2 \times 8 = 16$ 不是立方数，二者相合。

样例

输入：

plaintext

1
24
4 2 16 27

输出：

plaintext

$4 \times 2 = 8 = 2^3$ 、 $4 \times 16 = 64 = 4^3$ ，所以 4 号与 2、3 号都不合；而 $\{2, 16, 27\}$ 两两乘积 $32$ 、 $54$ 、 $432$ 都不是立方数，故答案为 3。

正解

思路

朴素做法是枚举全部数对，逐对判断乘积是否为完全立方数，再在冲突关系上求最大的两两相容子集。但 $n$ 达到 $10^5$ ，数对有约 $5 \times 10^9$ 个， $O(n^2)$ 完全不可行；而「最大相容子集」在一般冲突图上没有多项式算法。这提示我们：冲突条件是纯代数的，冲突图一定有特殊结构，整个优化就是把这个结构找出来。

第一步：立方核归约。 把每个数写成「完全立方数 × 立方核」，其中立方核是剥掉全部立方因子后剩下的部分——即每个素因子的指数对 3 取余后连乘。因为 $x \cdot y$ 为立方数当且仅当两个立方核的乘积为立方数（乘上的两个立方数不影响），所以只需按立方核给所有人分组，组内成员在冲突关系上完全等价。

第二步：冲突结构。 设 $f$ 是一个立方核（每个素因子指数 $\in \{0,1,2\}$ ）：

同核两两相容（ $f \ne 1$ ）： $f \cdot f$ 中每个出现的素因子指数为 $2e \in \{2,4\}$ ，都不是 3 的倍数，故不是立方数。
补核唯一：要 $f \cdot g$ 为立方数， $g$ 的每个素因子指数必须与 $f$ 的指数之和为 3 的倍数，所以 $f$ 中指数为 $e \in \{1,2\}$ 的素数 $p$ 在 $g$ 中只能取 $3-e$ ， $f$ 中不出现的素数在 $g$ 中也不出现，即 $g = \prod_{p \mid f} p^{3-e}$ 。这个 $g$ 自身也是立方核，且「取补」是对合运算（补的补是 $f$ ）。因此 $f$ 只与唯一的一个 $g$ 冲突，与其他任何核都不冲突。
核 1 特殊：核为 1 的数本身就是完全立方数，它们两两乘积仍是立方数，彼此全部冲突，只能留 1 人；但它与任何核 $\ne 1$ 的数都相合（立方数乘 $f$ 为立方 $\iff f = 1$ ）。

于是冲突图退化成若干互不相交的结构：每对互补核 $\{f, g\}$ 构成一个完全二分团（两侧的人全部互相冲突），外加核 1 自己的一个团，团与团之间没有任何边。各团独立，最优解就是：每对取人数多的一侧，核 1 取 1 人。这就是贪心，且由各团独立性直接最优。

第三步：高效求核与补。 $a_i \leqslant 2 \times 10^9$ ，而 $p^3 \leqslant 2 \times 10^9 \iff p \leqslant 1259$ ，立方因子只可能来自这 205 个素数。对它们试除并数清指数 $e$ ：先取 $e \bmod 3$ ，核乘 $p^{e \bmod 3}$ ；补要把指数补到 3 的倍数且保持立方核，故 $e \bmod 3 = 0$ 时补不乘，否则补乘 $p^{3-(e \bmod 3)}$ （指数为 1 时补 2，指数为 2 时补 1）。若试除中出现 $p^2 > x$ ，说明更小的素数都已除尽，剩余 $x$ 只能是 1 或素数，提前退出。走完全部 205 个素数后的剩余 $x$ 所有素因子都大于 1259，而大于 1259 的下一个素数是 1277， $1277^3 > 2 \times 10^9$ ，所以 $p^3$ 、 $p^2 q$ 、 $pqr$ 这些形式（都至少是 $p^3$ ）必然超界， $x$ 只可能是 $1$ 、 $p$ 、 $p^2$ 、 $pq$ ：用 isqrt 判断是否完全平方即可区分—— $x = p^2$ 时补乘 $\sqrt{x}$ ， $x = p$ 或 $pq$ （指数全为 1）时补乘 $x^2$ 。这样每个数最多 205 次取模，完全不需要对大剩余部分做范围试除。

下表把样例 1 的每个性格值分解成立方核并标出补核，展示冲突如何按核配对：

性格值	素因子分解	立方核 $f$	补核 $g$ （使 $f \cdot g$ 为立方）
4	$2^2$	4	2
2	$2^1$	2	4
16	$2^4 = 2^3 \cdot 2$	2	4
27	$3^3$	1	1

分组结果：核 2 有 2 人（性格值 2、16），核 4 有 1 人，核 1 有 1 人。配对 $\{2, 4\}$ 取人数多的核 2 侧得 2 人，核 1 取 1 人，合计 3 人，正对应样例选取的 $\{2, 16, 27\}$ 。注意 16 与 2 只差一个立方因子 $2^3$ ，所以同核而不冲突；27 是完全立方数，只与同样核为 1 的人冲突。

最后结算：用字典统计各核人数并记录每个核的补，遍历时用 taken 集合保证每对互补核只结算一次（补运算是对合，先遇到哪一侧结果相同），核 1 特判加 1，其余加 $\max(\text{cnt}[f], \text{cnt}[g])$ ；补核不在字典中时按 0 人处理。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 17:23
# update_at: 2026-10-02 17:23

import sys
from collections import Counter
from math import isqrt

# a_i ≤ 2×10⁹，而 p³ ≤ 2×10⁹ ⟺ p ≤ 1259：立方因子只可能来自这些素数
CUBE_PRIMES = [p for p in range(2, 1260) if all(p % d for d in range(2, isqrt(p) + 1))]  # 205 个


def kernel_pair(x: int) -> tuple[int, int]:
    """把性格值 x 拆成 (核, 补)：核是剥掉全部立方因子的 x，补使 核×补 恰为完全立方数。"""
    f = g = 1
    for p in CUBE_PRIMES:
        if x % p:
            if p * p > x:  # 更小的素数都除尽了，剩下的 x 只能是 1 或素数
                break
            continue
        e = 0
        while x % p == 0:  # 数清指数，顺便把 x 里的 p 除干净
            x //= p
            e += 1
        e %= 3  # 立方部分剥掉，核里只留对 3 取余的指数
        f *= p ** e
        if e:
            g *= p ** (3 - e)  # 补的指数补到 3，乘积里每个素因子的指数都是 3 的倍数
    # 收尾：剩余因子都 > 1259，x 只可能是 1、p、p²、p·q（p²q 已超过 2×10⁹）
    if x > 1:
        f *= x
        root = isqrt(x)
        g *= root if root * root == x else x * x  # p² 的补是 p；p 与 p·q 的补是各自的平方
    return f, g


def count_group(cnt: Counter[int], comp: dict[int, int]) -> int:
    """按互补核配对求和：每对取人数多的一侧，核为 1 的人两两冲突只能留 1 人。"""
    taken: set[int] = set()
    ans = 0
    for f, c in cnt.items():
        if f in taken:
            continue
        g = comp[f]  # comp 是对合：补的补还是 f，每对只在第一次遇到时结算
        taken.update((f, g))
        ans += 1 if f == 1 else max(c, cnt.get(g, 0))
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    cnt: Counter[int] = Counter()
    comp: dict[int, int] = {}
    for _ in range(n):
        a = next(data)
        f, g = kernel_pair(a)
        cnt[f] += 1
        comp[f] = g  # 同一个核的补唯一，重复赋值无害

    print(count_group(cnt, comp))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 21:53
 * update_at: 2026-10-04 21:53
 */

#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <iostream>

using namespace std;

typedef long long ll;

const int MAXP = 1260;          // 只需试除到 1259

vector<int> primes;             // 1260 以内的素数表

// 一个数的立方核与其互补核
struct Core {
    ll f;                       // 立方核：剥掉所有立方因子后剩下的部分
    ll g;                       // 互补核：与 f 相乘得到完全立方数的唯一立方核
};

// 筛出 2..1259 的所有素数
void init_primes() {
    static bool vis[MAXP];
    for (int i = 2; i < MAXP; i++) {
        if (!vis[i]) {
            primes.push_back(i);
            if ((ll)i * i < MAXP) {
                for (int j = i * i; j < MAXP; j += i) vis[j] = true;
            }
        }
    }
}

// 对 x 做质因数分解，去掉所有立方因子得到立方核 f，并算出互补核 g
Core reduce(ll x) {
    ll f = 1, g = 1;
    for (int i = 0; i < (int)primes.size(); i++) {
        int p = primes[i];
        if ((ll)p * p > x) break;            // 更小的素数都已除尽，x 剩余部分为 1 或大于 p 的素数
        if (x % p != 0) continue;
        int e = 0;
        while (x % p == 0) {
            x /= p;
            e++;
        }
        int r = e % 3;
        if (r == 1) {                        // 指数模 3 余 1：核留 p，补需要 p^2
            f *= p;
            g *= (ll)p * p;
        } else if (r == 2) {                 // 指数模 3 余 2：核留 p^2，补需要 p
            f *= (ll)p * p;
            g *= p;
        }
    }
    // 剩余部分所有素因子都大于 1259，只可能是 1、p、p^2 或 p*q
    if (x > 1) {
        ll s = sqrt((long double)x);
        while ((s + 1) * (s + 1) <= x) s++;
        while (s * s > x) s--;
        if (s * s == x) {                    // x = p^2，核指数取 2，补需要 p
            f *= x;
            g *= s;
        } else {                             // x = p 或 p*q，所有素因子指数均为 1
            f *= x;
            __int128 t = (__int128)g * x * x;
            g = (ll)t;
        }
    }
    return (Core){f, g};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    init_primes();

    int n;
    if (!(cin >> n)) return 0;

    map<ll, int> cnt;            // 每个立方核出现的次数
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        cnt[reduce(a).f]++;
    }

    ll ans = 0;
    set<ll> taken;               // 已经结算过的核，避免互补对重复计算
    for (map<ll, int>::iterator it = cnt.begin(); it != cnt.end(); ++it) {
        ll core = it->first;
        int c = it->second;
        if (taken.count(core)) continue;

        if (core == 1) {         // 核为 1 的数两两冲突，最多留 1 个
            ans += 1;
            taken.insert(1);
            continue;
        }

        ll other = reduce(core).g;          // core 的互补核
        int c2 = 0;
        map<ll, int>::iterator jt = cnt.find(other);
        if (jt != cnt.end()) c2 = jt->second;

        ans += max(c, c2);                  // 每对互补核取人数较多的一侧
        taken.insert(core);
        taken.insert(other);
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间：每个数最多试除 $\pi(1259) = 205$ 个素数，总复杂度 $O(205n) = O(n)$ ；分组与配对结算各 $O(n)$ 。与 C++ 标准解（试除 $\leqslant 1260$ 的素数 + map 计数）同阶。
空间： $O(n)$ ，用于输入数组与核计数字典，实测峰值约 36MB。
Python 风险：最坏情形（ $10^5$ 个接近 $2 \times 10^9$ 的素数，每个数走满 205 次取模）实测 0.70s，OJ 限时 1000ms 下有 TLE 风险，本地放宽限时内全部数据通过。

总结

本题的核心是把「乘积为完全立方数」这一冲突条件翻译成代数结构：先剥立方因子归约到立方核，冲突判据就只取决于核；再发现每个核有唯一互补核，冲突图随之退化为若干互不相交的二分团，最大兴趣组按团贪心即得。

三个容易踩的边界：

核 1 的人两两冲突，只能留 1 人，但与所有其他人都相容；
取补后要把两侧人数取较大值，补核可能根本没在数据中出现（按 0 人处理）；
只试除 $p \leqslant 1259$ 就够了，剩余部分靠 isqrt 判平方区分 $p^2$ 与 $p$ 、 $pq$ ，无需大范围试除。

牛牛的最大兴趣组

目录

形式化题目

样例

正解

思路

代码

复杂度

总结