ykw 的数字接龙
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
ykw 最近很喜欢玩成语接龙，有一天他突发奇想能不能和小伙伴玩一个数字接龙？
他决定尝试设计一种有趣的数字接龙，规则如下：
有 $n$ 个合数，每个数都可以被表示成 $x = p * q$ 的形式($p,q$为两个互异质数)
若 $a = p1 * q1, b = p2 * q2$ 满足 $p1 < q1, p2 < q2, q1 == p2$ 时候 ykw 认为 $b$ 可以接在 $a$ 的后面
现在 ykw 想知道这 $n$ 个数字中最多能选出几个数字成为一个接龙序列？
输入格式
输入第一行包含一个正整数 $n$，表示数字个数
输入第二行包含 $n$ 个合数 $a_1, a_2 \dots a_n$。
对于 $30\%$ 的数据满足：$n \leq 10, a_i \leq 1000$
对于 $60\%$ 的数据满足：$n \leq 1000, a_i \leq 10^6$
对于 $100\%$ 的数据满足：$n \leq 50000, a_i \leq 10^6$
输出格式
输出一行，表示最多能选出的数字个数。
样例
9
10 6 22 15 21 35 77 119 1875提示
最长接龙序列为 $6,15,35,77,187$
20240216提高组班级模拟赛
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2024-2-16 16:00
- 结束于
- 2024-2-26 16:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 12
