额。。VIJOS复活了。。所以我去A了这道题。。www.vijos.cn/Problem_Show.asp
题目是说给你n个数，都小于10^5，然后让你求出其中一个子序列（连不连续无所谓，只要顺序是原序列的顺序就OK）。。 相邻两个数不互质。。让你求这个序列的最大长度。。n<=100000
很明显暴力DP是会悲剧的，如果你用Dpi表示第i个数结尾的最长长度然后O(n)枚举前一个的话是O(n^2)的。关键是利用题目的性质。
注意到不互质的数一定有一个公共的质因子，就简单了。首先算出10^5一下每个质数，然后开个数组保存每个当前以第i个质数的倍数结尾的数列的最长值，然 后对于每个数枚举他的每个质因子计算并更新一下就可以了。。
关键是一个数的质因子数目显然是O(logn)级别的，并且预先处理也可以大大降低枚举量。。我感觉应该会很快，没想到0ms秒杀，爽额。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000+1,maxp=maxn>>3;
bool NotPrime[maxn]={0};
int Ps[maxp],cnt=0;
void GetPrime()
{
for(int i=2;i*i<maxn;i++)
{
if(!NotPrime[i])
{
for(int j=i*2;j<maxn;j+=i)
NotPrime[j]=true;
}
}
for(int i=2;i<maxn;i++)
if(!NotPrime[i])
Ps[cnt++]=i;
}
int Max[maxp],pnt,Tmp[1000];
void GetDiv(int p)
{
pnt=0;
for(int i=0;i<cnt;i++)
{
int t=Ps[i];if(t*t>p)break;
if(p%t==0)
{
Tmp[pnt++]=i;
while(p%t==0)p/=t;
}
}
if(p!=1)
{
int i=lower_bound(Ps,Ps+cnt,p)-Ps;
Tmp[pnt++]=i;
}
}
void solve()
{
int n,x;scanf("%d",&n);
while(n–)
{
scanf("%d",&x);
GetDiv(x);
int ret=0;
rep(i,pnt)ret=max(ret,Max[Tmp[i]]);
ret++;
rep(i,pnt) Max[Tmp[i]]=ret;
}
int ans=0;
rep(i,cnt) ans=max(ans,Max[i]);
printf("%dn",ans);
}
int main()
{
//freopen("in","r",stdin);
GetPrime();
solve();
}