前言

比赛的时候只得了80分，想不出怎么优化，看了榜1大佬的思路明白了一些东西，才有了这篇题解(⊙﹏⊙)

题目描述

解题思路

1.容易看出，我们可以将数组排序后，进行dp，假设当前位置是第i个数，可以枚举前i-1个数，取与i的最大公约数大于1的数j，则f[i]=max(f[i],f[j]+1).这样可以得80分。(其余两个点超时)
2.接下来就需要考虑怎样优化dp的过程，暴力的方法一大部分时间花在
了枚举前i-1个数上，如果我们分解质因数，每次转移只需要枚举这个数的质因子即可。

AC代码

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define maxn 100010
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int MOD=1000000007;
const double pi=acos(-1.0);
inline int lowbit(int x){ return x&(-x);}
int a[maxn],mx[maxn],f[maxn]; //mx[i]表示i的最大质因子，f[i]表示以i结尾的序列的长度
int p[maxn]; //p存枚举到的数的质因子
bool vis[maxn];
int main()
{
    io;
    //用埃氏筛找每个数的最大质因子，找最大值因子而不是最小质因子是为了方便质因数分解
    for(int i=2;i<maxn;i++){
        if(vis[i]) continue;
        for(int j=i;j<maxn;j+=i){
            vis[j]=true;
            mx[j]=i;
        }
    }

    int t;
    cin>>t;
    while(t--){
        memset(f,0,sizeof(f));
        int n,ans=0;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            int r=0,maxx=0;
            //枚举每一个质因子，找以a[i]结尾的序列最大长度
            while(a[i]>1){
                int tmp=mx[a[i]];
                while(a[i]%tmp==0) a[i]/=tmp;
                p[++r]=tmp; //保存该数的质因子
                maxx=max(maxx,f[tmp]+1);
                ans=max(ans,maxx);
            }
            //更新以该数质因子结尾的序列长度，如在样例1中，遍历到2时，f[2]=1，遍历到3时，f[3]=1
            //遍历到6时，f[2]=3(因为还有4),f[3]=2，一个数对每一个以其质因子结尾的序列都会有贡献
            for(int j=1;j<=r;j++) f[p[j]]=max(f[p[j]],maxx);
        }
        cout<<ans<<endl;
    }
    return 0;
}