Problem1816--最长互质子序列（动规课程B）（4.2）

1816: 最长互质子序列（动规课程B）（4.2）

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 1Submit: 3Statistics

Description

求一个数列中最长互质子序列的长度的问题。 互质子序列要求所有相邻的 2 个数最大公约数为 1。 例如数列： 1 7 2 8 3 4 ， 它的最长互质子数列就是 1 7 2 3 4。

Input

第一行一个数 n， 范围[1..1000]；
第二行 n 整数，范围[1..1000000]；

Output

一个整数，为最长互质子序列的长度。

Sample Input Copy 

6
9 8 6 7 20 10

Sample Output Copy 

4

Source/Category

动态规划 
Submit