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;
}