A7013. Good Sequences
编程题
普及+/提高
知识点
题目描述
松鼠 Liss 对数列很感兴趣。她也有自己喜欢的整数。她认为 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ 是好的整数。
现在她感兴趣于好的数列。一个数列 $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$ 的最大公约数）。
- 数列中的所有元素都是好的整数。
请你求出最长好的数列的长度。
现在她感兴趣于好的数列。一个数列 $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$ 是严格递增的。