301407: CF264B. Good Sequences
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Good Sequences
题意翻译
松鼠丽丝对序列很感兴趣,她对整数也有着爱好。它特别喜欢n个她称之为“好整数”的整数:a1,a2,……,an。(会输入) 现在,她对“好序列”很感兴趣。如果一个序列x1,x2,...,xk能够满足一下三个条件,那就是一个“好序列”: 1.该序列是严格上升的,即x[i] < x[i+1](1<=i<=k-1) 2.任意两个相邻的元素是非互质的,即gcd(x[i],x[i+1]) > 1 (1<=i<=k-1) (gcd即最大公约数) 3.所有的数字都是“好整数” 现在,请你找出长度最长的“好序列” Translated by @Qi_XingZhi题目描述
Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks $ n $ integers $ a_{1},a_{2},...,a_{n} $ are good. Now she is interested in good sequences. A sequence $ x_{1},x_{2},...,x_{k} $ is called good if it satisfies the following three conditions: - The sequence is strictly increasing, i.e. $ x_{i}<x_{i+1} $ for each $ i $ $ (1<=i<=k-1) $ . - No two adjacent elements are coprime, i.e. $ gcd(x_{i},x_{i+1})>1 $ for each $ i $ $ (1<=i<=k-1) $ (where $ gcd(p,q) $ denotes the greatest common divisor of the integers $ p $ and $ q $ ). - All elements of the sequence are good integers. Find the length of the longest good sequence.输入输出格式
输入格式
The input consists of two lines. The first line contains a single integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of good integers. The second line contains a single-space separated list of good integers $ a_{1},a_{2},...,a_{n} $ in strictly increasing order ( $ 1<=a_{i}<=10^{5}; a_{i}<a_{i+1} $ ).
输出格式
Print a single integer — the length of the longest good sequence.
输入输出样例
输入样例 #1
5
2 3 4 6 9
输出样例 #1
4
输入样例 #2
9
1 2 3 5 6 7 8 9 10
输出样例 #2
4