暴力\(DP\)
先考虑暴力\(DP\)该怎么写。
因为每个序列之后是否能加上新的节点只与其结尾有关，因此我们设\(f_i\)为以\(i\)为结尾的最长序列长度。
每次枚举一个前置状态，判断是否合法之后进行转移。
优化\(DP\)
上面做法的瓶颈在于，判断是否合法需要大量时间。
则有一个比较巧妙的做法。
首先对于每一个数\(a_i\)，\(\sqrt {max_{x=1}^na_x}\)范围内的某一质数\(j\)，我们求出\(p_{i,j}\)表示\(a_i\)是否含有质因数\(j\)。
然后，再对与每一个数\(a_i\)，我们用\(s_i\)存下其大于\(\sqrt{max_{x=1}^na_x}\)的质因数，若没有则\(s_i=1\)。
那么，我们可以用\(g_x\)表示所有的\(a_i\)含有质因数\(x\)的\(f_i\)的最大值，用\(Mx_x\)表示所有的\(s_i=x\)的\(f_i\)的最大值\((x!=1)\)，然后记下\(MP\)和\(MP\_\)分别表示\(Mx_x\)的最大值和次大值所对应的\(x\)。
转移时我们可以从所有当前\(a_i\)不含的质数所对应的\(g\)转移，然后若\(s_i=MP\)，则从\(Mx_{MP\_}\)转移，否则从\(Mx_{MP}\)转移。
具体实现时我们可以把\(g_x\)中\(x\)的定义改为第\(x\)个质数。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define M 1000000
#define SM 1000
#define Gmax(x,y) (x<(y)&&(x=(y)))
using namespace std;
int n,a[N+5];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
char c,*A,*B,FI[FS];
public:
I FastIO() {A=B=FI;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}F;
template<int SZ> class LinearSiever//线性筛筛质数
{
public:
int Pt,P[SZ+5];
I LinearSiever()
{
RI i,j;for(i=2;i<=SZ;++i) for(!P[i]&&(P[++Pt]=i),
j=1;j<=Pt&&1LL*i*P[j]<=SZ;++j) if(P[i*P[j]]=1,!(i%P[j])) break;
}
};
class PrimeSolver
{
private:
int f[N+5],g[SM+5],Mx[M+5],s[N+5],p[N+5][SM+5];LinearSiever<SM> P;
I void Init(CI x)//初始化，质因数分解预处理每个数
{
RI i;for(s[x]=a[x],i=1;i<=P.Pt;++i)
{
if(s[x]%P.P[i]) continue;p[x][i]=1;
W(!(s[x]%P.P[i])) s[x]/=P.P[i];
}
}
public:
I void Solve()
{
RI i,j,MP=0,MP_=0,ans=0;for(i=1;i<=n;++i)//DP
{
for(Init(i),f[i]=0,j=1;j<=P.Pt;++j) !p[i][j]&&Gmax(f[i],g[j]+1);//从当前a[i]不含的质数转移
MP^s[i]?Gmax(f[i],Mx[MP]+1):Gmax(f[i],Mx[MP_]+1);//从Mx处转移
for(j=1;j<=P.Pt;++j) p[i][j]&&Gmax(g[j],f[i]);if(s[i]==1||f[i]<=Mx[s[i]]) continue;//更新g值
Mx[s[i]]=f[i],MP^s[i]&&(Mx[MP]<f[i]?(MP_=MP,MP=s[i]):Mx[MP_]<f[i]&&(MP_=s[i]));//更新Mx值，并更新MP和MP_
}
for(i=1;i<=n;++i) Gmax(ans,f[i]);printf("%d",ans);//统计并输出答案
}
}S;
int main()
{
freopen("demon.in","r",stdin),freopen("demon.out","w",stdout);
RI i;for(F.read(n),i=1;i<=n;++i) F.read(a[i]);return S.Solve(),0;
}