A7013 | Good Sequences
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
松鼠 Liss 对数列很感兴趣。她也有自己喜欢的整数。她认为 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ 是好的整数。
现在她感兴趣于好的数列。一个数列 $x_{1},x_{2},...,x_{k}$ 被称作“好”的当且仅当它满足以下三个条件：
现在她感兴趣于好的数列。一个数列 $x_{1},x_{2},...,x_{k}$ 被称作“好”的当且仅当它满足以下三个条件：
- 这个数列是严格递增的，即对每个 $i$ 满足 $1 \leq i \leq k-1$，都有 $x_{i} x_{i+1}$。
- 任意相邻的两个元素都不是互质的，即对每个 $i$ 满足 $1 \leq i \leq k-1$，都有 $gcd(x_{i},x_{i+1}) 1$（其中 $gcd(p, q)$ 表示整数 $p$ 和 $q$ 的最大公约数）。
- 数列中的所有元素都是好的整数。
输入格式
第一行包含一个整数 $n$，表示原序列中整数的个数。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$，表示给定的严格递增序列。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$，表示给定的严格递增序列。
输出格式
输出一个整数，表示最长好的数列的长度。
输入输出样例
输入 #1
5 2 3 4 6 9
输出 #1
4
输入 #2
9 1 2 3 5 6 7 8 9 10
输出 #2
4
【样例解释 1】
原序列为 $\{2, 3, 4, 6, 9\}$。
我们可以构造出如下长度为 4 的和谐序列：
$\{2, 4, 6, 9\}$
验证相邻元素：
- $\gcd(2, 4) = 2 1$
- $\gcd(4, 6) = 2 1$
- $\gcd(6, 9) = 3 1$
满足条件。其他可能的序列如 $\{2, 4, 6\}$ 或 $\{3, 6, 9\}$ 长度均为 3，不如 4 优。
【数据范围】
对于 $100\%$ 的数据，满足：
- $1 \le n \le 10^5$
- $1 \le a_i \le 10^5$
- 保证输入序列 $a$ 是严格递增的。
原序列为 $\{2, 3, 4, 6, 9\}$。
我们可以构造出如下长度为 4 的和谐序列：
$\{2, 4, 6, 9\}$
验证相邻元素：
- $\gcd(2, 4) = 2 1$
- $\gcd(4, 6) = 2 1$
- $\gcd(6, 9) = 3 1$
满足条件。其他可能的序列如 $\{2, 4, 6\}$ 或 $\{3, 6, 9\}$ 长度均为 3，不如 4 优。
【数据范围】
对于 $100\%$ 的数据，满足：
- $1 \le n \le 10^5$
- $1 \le a_i \le 10^5$
- 保证输入序列 $a$ 是严格递增的。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？