题目描述

给定一个长度为 $n$ 的严格单调递增整数序列 $a_1, a_2, \dots, a_n$，找出该序列的一个最长子序列，要求该子序列中任意两个相邻元素不互质。输出满足条件的最长子序列的长度。

数据范围

• $1 \leq n \leq 10^5$
• $1 \leq a_i \leq 10^5$
• $a_i < a_{i+1}$

思路

题目要求找到一个子序列，使得子序列中任意两个相邻元素的GCD大于1，由于序列是严格递增的，直接dp！

定义 $dp[i]$ 表示以 $a_i$ 结尾的最长满足条件的子序列的长度。初始时，$dp[i] = 1$，因为每个元素本身就是一个长度为 1 的子序列

对于每个 $a_i$，我们需要找到前面所有满足 $\gcd(a_i, a_j) > 1$ 的 $a_j$，并更新 $dp[i]$ 为 $dp[j] + 1$ 的最大值

注意直接使用双重循环会导致时间复杂度为 $O(n^2)$，而本题数据范围$n = 10^5$，所以，不出意外，TLE 15/20需要优化

那么怎么办呢

其实只要质因数分解就彳亍了，对于每个 $a_i$，分解其质因数。如果两个数有共同的质因数，则它们的GCD大于 1
另外注意用哈希记录，记录每个质因数对应的最大子序列长度。对于每个 $a_i$，遍历其所有质因数，找到记录的最大值，更新 $dp[i]$和哈希表

时间复杂度

$O(n \log \max a)$

CODE

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cmath>

using namespace std;

vector<int> pf(int x) {
    vector<int> f;

    for (int i = 2; i <= sqrt(x); i ++) {
        if (x % i == 0) {
            f.push_back(i);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) f.push_back(x);

    return f;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i ++) cin >> a[i];

    vector<int> dp(n, 1);
    unordered_map<int, int> pm;

    for (int i = 0; i < n; i ++) {
        vector<int> f = pf(a[i]);
        int ml = 0;
        for (int p : f) {
            if (pm.count(p)) ml = max(ml, pm[p]);
        }
        dp[i] = ml + 1;
        for (int p : f) pm[p] = max(pm[p], dp[i]);
    }

    cout << *max_element(dp.begin(), dp.end()) << endl;

    return 0;
}