AT_agc003_d.[AGC003D] Anticube

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君在生日时从妈妈那里收到了 $s_1,\ldots,s_N$ 这 $N$ 个正整数。注意，这些数中可以有重复的元素。高桥君打算从中选出若干个整数，用圆圈圈起来。

高桥君讨厌立方数，因此，如果 $s_i$ 和 $s_j$ （ $i \neq j$ ）都被圈起来了，那么它们的乘积 $s_i s_j$ 不能是立方数。例如，当 $s_1=1,s_2=1,s_3=2,s_4=4$ 时， $s_1$ 和 $s_2$ 不能同时被圈起来。同样， $s_3$ 和 $s_4$ 也不能同时被圈起来。

请你求出高桥君最多能圈起多少个整数。

输入格式

输入以如下格式从标准输入中给出。

$N$ $s_1$ $s_2$ $\ldots$ $s_N$

输出格式

输出高桥君最多能圈起来的整数个数。

输入输出样例

输入#1
```
8
1
2
3
4
5
6
7
8
```
输出#1
```
6
```
输入#2
```
6
2
4
8
16
32
64
```
输出#2
```
3
```

输入#3

10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999

输出#3

说明/提示

限制条件

$1 \leq N \leq 10^5$
$1 \leq s_i \leq 10^{10}$
所有输入均为整数。

样例解释 1

可以圈起 $1,2,3,5,6,7$ 这几个数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页