dp【小L的数列】

思路参考https://blog.nowcoder.net/n/cc6fda3807314f7fbbd3ebd63571d88c
整体算法就是：
1.排序
2.循环因子找到最大的dp[i]
3.更新所有因子答案为mx+1
4.找到最大的ans

#include <bits/stdc++.h>
#define MAXN 110000
using namespace std;
int a[MAXN], dp[MAXN], T, n;
int main(){
    scanf("%d",&T);
    while(T--){
        int res = 0;
        scanf("%d", &n);
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<n;i++)    scanf("%d", &a[i]);
        sort(a, a+n);
        for(int i=0;i<n;i++)
        {
            int tmpmax = 0, left = a[i];
            for(int j=2;j*j<=a[i];j++){
                if(a[i] % j != 0)   continue;
                if(dp[j] > tmpmax) tmpmax = dp[j];
                while(left % j == 0)    left = left / j;
            }
            if(left != 1 && dp[left] > tmpmax)  tmpmax = dp[left];
            for(int j=2;j*j<=a[i];j++)
                if(a[i] % j == 0)   dp[j] = tmpmax + 1;
            if(left != 1)    dp[left] = tmpmax + 1;
            if(tmpmax + 1 > res)    res = tmpmax + 1;
        }
        printf("%d\n", res);
    }
    return 0;
}