思路参考：https://blog.nowcoder.net/n/7937ea0fe884441994a04e9f91cd9a8f

先对数组排序，问题变成寻找满足条件的最长子序列，很容易联想到dp。于是有了一个基础的动态转移方程：
图片说明
其中表示以第个数为最后一个元素构造的序列中最大的序列长度。
这是一个的算法，只能得80分。

为了优化，可以从质因数分解的角度考虑。设为因式包含的最大序列长度，换句话说，如果有一个合法的序列中其中一个元素包含了因子，那就可以将这个序列纳入考虑范围。以如下数据为例：

2 3 4 6 9

其中的一个合法的序列为：

2 4 6 9

2包含2，4包含2，6包含2和3,9包含3，因此整个序列包含了{2,3}，因此和就至少为4（当然这就是最后答案）。

我们需要在循环元素的过程中不断更新数组的值。例如，当遇到6时，6包含因数2和3，我们观察到先前的值为2，的值为1，现在我们可以把6接在包含2和3因子的序列后面，因此、都要更新为，也就是3。

按照这种思路，整体算法就是：

  1. 排序；
  2. 循环元素:
    (1) 寻找当前元素的所有因子，找出其中最大的值；
    (2) 将当前元素所有的因子i对应的更新为；
  3. 找出最大的。

一个细节是，我们仅需要枚举质因子就足够了，不过本题考虑到因子层面也就可以通过了，整体的时间复杂度为。

代码如下：

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