thz 的神奇零食柜
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
thz 家里屯了非常多的零食，他家里一共有 $n$ 种零食，根据 thz 自己订制的各种规则，最后依次排成一排放在一个大柜子里
现在 thz 觉得 $n$ 种零食摆成一排太占地方了，于是他准备买一些零食柜将这 $n$ 种零食分开存放
这种零食柜非常神奇，只要存在这个零食柜里的零食满足一定的条件，里面的零食将永不过期！
条件是这样的：如果每种零食都有一个特殊的存储值 $a_i$，只要某个零食柜里的任意两种零食的存储值之积不是完全平方数（这里我们认为 $1$ 也是完全平方数），那么这个零食柜里的零食将永不过期
但是 thz 很懒，他不想改变他好不容易排成一排的零食顺序，所以他只想把这 $n$ 个零食分成好几段，每段零食都用一个零食柜存储
现在 thz 想知道，他最少需要买几个神奇零食柜？
输入格式
输入第一行包含一个正整数 $n$，表示有 $n$ 种零食接下来一行包含 $n$ 个整数 $a_i$，分别表示每种零食的存储值 $a_i$
对于 $30\%$ 的数据： $1 \leq n \leq 100, 1 \leq a_i \leq 100$
对于 $60\%$ 的数据： $1 \leq n \leq 100000$
对于 $100\%$ 的数据：$1 \leq n \leq 200000, 1 \leq a_i \leq 10^8$
对于 $60\%$ 的数据： $1 \leq n \leq 100000$
对于 $100\%$ 的数据：$1 \leq n \leq 200000, 1 \leq a_i \leq 10^8$
输出格式
输出一个整数，表示 thz 最少需要购买的神奇零食柜数量样例
5
9 2 2 3 1220240324提高组班级模拟赛
- 状态
- 已结束
- 规则
- IOI
- 题目
- 3
- 开始于
- 2024-3-24 11:30
- 结束于
- 2024-4-3 11:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 9
