3598: 牛牛的最大兴趣组(第一轮03)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：2
题目描述
牛牛的班级中有 n 个人，他们的性格各不相同。
牛牛现在想要从这 n 个人中选出一些人组成一个兴趣小组，但是他想让参加这
个兴趣小组的人数尽可能的多。但是他有不想让其中有任何一对人之间由于性格
问题产生矛盾。
具体来说，如果这个兴趣小组中出现两个人性格值的乘积开三次方根是一个正整
数，就认为他们两个性格不合。
比如一个性格值为 2 的同学和一个性格值为 4 的同学就是性格不合的，因为
2*4=8，而一个性格值为 2 的同学和一个性格值为 8 的同学性格相合，可以出现
在同一个兴趣小组中，因为 2*8=16，16 开三次方根不是一个正整数。
请你告诉牛牛，他们班的同学组成的最大兴趣小组的人数是多少。
输入
第一行输入一个正整数 n 表示牛牛所在的班级中的人数。
接下来输入一行 n 个正整数𝑎𝑖表示每个人的性格值
输出
输出一行一个正整数，表示最大兴趣小组的人数。
样例输入 复制
4
4 2 16 27样例输出 复制
3提示
【样例 1 说明】
1 号和 2 号同学性格值的乘积为8 = 2
3，性格不合，1 号和 3 号同学性格值的乘
积为64 = 4
3 ，性格不合。
选取第 2,3,4 号同学组成一个最大兴趣组，共 3 人。
【数据范围】
对于10%的测试数据，保证1 ≤ 𝑛 ≤ 10,1 ≤ 𝑎𝑖 ≤ 500
对于20%的测试数据，保证1 ≤ 𝑛 ≤ 10,1 ≤ 𝑎𝑖 ≤ 109
对于30%的测试数据，保证1 ≤ 𝑛 ≤ 150,1 ≤ 𝑎𝑖 ≤ 2 × 109
对于40%的测试数据，保证1 ≤ 𝑛 ≤ 1000,1 ≤ 𝑎𝑖 ≤ 2 × 109
对于100%的测试数据，保证1 ≤ 𝑛 ≤ 105,1 ≤ 𝑎𝑖 ≤ 2 × 109