可爱捏
题意
给出 \(n\) 个整数 \(a_i(1\le i\le n)\)。
求最多选出多少个数，使她们两两的乘积不为完全立方数。
\(n\le 10^5,a_i \le 10^5\)。
思路
可以先将 \(a_i\) 分解质因数，将所有指数 \(\bmod 3\)，两个数相乘为完全平方数即对应指数相加等于 \(3\)。
由此可知对于每个数，和她相乘等于完全立方数的数是唯一确定的。
如果我们能求出指数 \(\bmod 3\) 后的值和对应的数，就能简单的算出答案。
发现每对数之间互相独立，只需要选择数量多的一个即可。
但 \(O(n\sqrt V)\) 的时间去分解质因数会 TLE，考虑优化。
由于我们求的是指数 \(\bmod 3\) 后的数，只有小于等于 \(\sqrt[3]{V}\) 的质因数的指数才有可能大于等于 \(3\)，
我们只需要暴力求出小于等于 \(\sqrt[3]{V}\) 的质因数，其他分类讨论。
记 \(x\) 表示 \(a_i\) 除掉所有小于等于 \(\sqrt[3]{V}\) 的质因数后剩下的数，
我们发现 \(x\) 最多由两个质数组成，用反证法容易证明：
若 \(x=pqr\)，根据 \(p,q,r > \sqrt[3]{x}\)，有 \(pqr > x\)，矛盾。
分类讨论：
-
\(x=1\)；
-
\(x\) 由两个相同质数组成；
-
\(x\) 由一个或两个不同质数组成。
乘上对应的数即可。
时间复杂度：\(O(n\sqrt[3]{V}+n\log n)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, s[N], ans;
map <int, int> cnt, ne;
set <int> used;
vector <int> _;
signed main() {
freopen("lovely.in", "r", stdin);
freopen("lovely.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> s[i];
for (int i = 1, c; i <= n; i ++) {
int x = 1, y = 1, t = s[i]; // x;指数 mod 3 后的数 y:x对应的数
for (int j = 2; j * j * j <= s[i]; j ++) { // 暴力分解
for (c = 0; t % j == 0; t /= j, c = (c + 1) % 3);
for (int k = 1; c && k <= c; k ++) x *= j;
for (int k = 1; c && k <= 3 - c; k ++) y *= j;
}
if ((int)sqrt(t) * (int)sqrt(t) == t) y *= sqrt(t); // 分类讨论
else y *= t * t;
x *= t, cnt[x] ++, ne[x] = y, _.push_back(x);
}
for (auto x : _) {
if (x == 1) continue;
if (used.count(x) || used.count(ne[x])) continue;
ans += max(cnt[x], cnt[ne[x]]); // x 和 x 对应的数只能取一个 个数较大的
used.insert(x); used.insert(ne[x]);
}
cout << ans + (cnt[1] > 0) << "\n";
return 0;
}