思路参考: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;
}