Codeforces 264 B. Good Sequences

B. Good Sequences
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a1, a2, ..., an are good.

Now she is interested in good sequences. A sequence x1, x2, ..., xk is called good if it satisfies the following three conditions:

  • The sequence is strictly increasing, i.e. xi < xi + 1 for each i (1 ≤ i ≤ k - 1).
  • No two adjacent elements are coprime, i.e. gcd(xi, xi + 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.

Input

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 105) — the number of good integers. The second line contains a single-space separated list of good integers a1, a2, ..., an in strictly increasing order (1 ≤ ai ≤ 105; ai < ai + 1).

Output

Print a single integer — the length of the longest good sequence.

Examples
input
5
2 3 4 6 9
output
4
input
9
1 2 3 5 6 7 8 9 10
output
4
Note

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

题目链接

题意 

给一个严格递增的序列,求出最长的相邻元素不互质的递增序列。

分析 

不互质则必有相同的因子,那么只要相邻的有相同的因子,那么就可以一段拼一段,从而拼出最长的。先预处理每个数的因子,对于当前序列,处理每个数的因子出现的次数,用来更新维护dp[i](最后一对元素的公共因子为i的最长长度),即先从该数的所以因子中选出dp值最大的那个,这就说明当前这个数可以拼接上去,形成新的序列,长度+1,此时再更新当前数的所有因子的dp值。最后再遍历一边,找出最大长度。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn = 1e5+;
const int mod = +;
typedef pair<int,int> pii;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ms(a,b) memset(a,b,sizeof(a))
vector<int> p[maxn];
int n;
void init(){
for(int i=;i<maxn;i++){
for(int j=i;j<maxn;j+=i){
p[j].pb(i);
}
}
}
int a[maxn];
int d[maxn];
int main(){
// freopen("in.txt","r",stdin);
init();
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d",&a[i]);
for(int i=;i<n;i++){
int maxx=;
for(int j=;j<p[a[i]].size();j++){
// cout<<p[a[i]][j]<<" ";
maxx = max(maxx,d[p[a[i]][j]]);
}
for(int j=;j<p[a[i]].size();j++){
d[p[a[i]][j]]=maxx+;
}
// puts("");
}
int maxx = ;
for(int i=;i<maxn;i++) maxx = max(maxx,d[i]);
cout<<maxx;
return ;
}
上一篇:Fuck me 忘记改REDO 造成复制用户超级慢


下一篇:Socket 通信(基础原理、实时聊天系统雏形)