题目：http://codeforces.com/problemset/problem/264/B
题意：给你一个递增序列，然后找出满足两点要求的最长子序列
第一点是a[i]>a[i-1]
第二点 gcd(a[i],a[i-1])>1 也就是说两个数不能互质
找出最长的子序列长度
思路：首先想互质问题，如果两个数互质说明两个数之间没有素因子相同，我们想以每个素因子结尾的最大长度是多少
然后比如样例 2 3 4 6 9
第一个数 2 2结尾 1
第二个数 3 3结尾 1
第三个数 4 2结尾 2
第四个数6 拆分因子有 2，3 2结尾 3， 3结尾2 ，但是这个时候我以6结尾，那么其实3这个位置长度也是3了，
（所以，我们要找出最大的那个长度，再重新赋值到这个数的每个素因子上） 这个时候就能解出来了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iostream>
#include<map>
#define mod 1000007
#define maxn 200001
using namespace std;
typedef long long ll;
ll a[maxn];
ll dp[maxn];
ll n;
int main(){
cin>>n;
for(int i=;i<n;i++){
cin>>a[i];
}
for(int i=;i<n;i++){
ll z=a[i];
map<ll,ll> mp;
vector<int> q;
while(z!=){
ll t=(ll)sqrt((double)z);//必须要加，不然会超时
ll j=;
for(;j<=t;j++){
if(z%j==){
if(mp[j]==) q.push_back(j);
mp[j]++;
z/=j;
break;
}
}
if(j==t+){
if(mp[z]==) q.push_back(z);//判断素数情况
break;
}
}
ll mx=-;
for(int j=;j<q.size();j++){//找出最大长度
dp[q[j]]++;
if(mx==-) mx=dp[q[j]];
else mx=max(mx,dp[q[j]]);
}
for(int j=;j<q.size();j++){//重新赋到每一个位置
dp[q[j]]=mx;
}
}
ll x=dp[];
for(int i=;i<maxn;i++){
x=max(x,dp[i]);
}
cout<<max((ll),x);
}