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.

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).

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

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 ;

}