Good Sequences
状态很显然，设 \(f[i]\) 表示位置 \(i\) 的最长长度。
关键是转移，暴力转移是 \(O(n^2)\) 的，我们必须找到一个更优秀的转移。
因为一个数的质因子数量是 \(O(\log n)\) 的，而只有和这个数具有相同质因子的数是可以转移的；
因此我们可以对于每个质数 \(p\)，设一个 \(mx_p\) 表示所有有 \(p\) 作为质因子的 \(x\) 的 \(f_i\) 的最大值。
关于质因子应该怎么得出嘛，线性筛一下即可。
复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n,res,t,x;
int p[N],pre[N],mx[N],f[N];
void prime(){
for(int i=2;i<=N;i++){
if(!p[i]){p[++p[0]]=i;pre[i]=p[0];}
for(int j=1;j<=p[0]&&i*p[j]<=N;j++){
p[i*p[j]]=true;
pre[i*p[j]]=j;
if(!(i%p[j])) break;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
prime();
for(int i=1;i<=n;i++){
cin>>x;
f[i]=1;
t=x;
while(t!=1){
f[i]=max(f[i],mx[pre[t]]+1);
t/=p[pre[t]];
}
t=x;
while(t!=1){
mx[pre[t]]=f[i];
t/=p[pre[t]];
}
res=max(res,f[i]);
}
printf("%d\n",res);
return 0;
}