好序列（最长合法序列）

好序列

题目描述

给定 n 个严格递增的数 a1, a2, …, an，从中选取一个子序列 x1, x2, …, xk，满足：

• x1 < x2 < … < xk（严格递增）
• gcd(xi, xi+1) > 1（相邻元素有公共质因子）
• xi 必须在给定的数组 a 中

求最长序列的长度。

解题思路

核心观察

1. 相邻元素有公共质因子：两个数能相邻的条件是它们至少共享一个质因数。

2. 动态规划：对于每个数 ai，考虑它能接在哪些数后面。以 ai 的质因数为”桥梁”，如果某个质因数 p 之前出现过，那么以 p 结尾的最长序列长度 +1 就是以 ai 结尾的长度。

3. 状态转移：

   • 设 dp[p] 表示以质因数 p 结尾的最长序列长度
   • 对于 ai，计算其所有质因数集合 fac
   • cur = max(dp[p] for p in fac) + 1
   • 更新所有 dp[p] = cur

4. 特殊处理：如果 ai = 1（没有质因数），则单独成为一个新的序列，长度为 1。

算法步骤

1. 预处理：计算每个数的质因数集合
2. 遍历数组，对于每个数：
   • 获取其质因数集合
   • 如果非空，取最大 dp 值 +1
   • 更新 dp 字典
3. 记录最大长度

代码实现

n = int(input())
arr = [int(x) for x in input().split()]

def prime_factors(n):
    """返回 n 的所有质因数（去重）"""
    factors = set()
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.add(d)
            n //= d
        d += 1
    if n > 1:
        factors.add(n)
    return factors

ans = 0
dp = {}

for i in range(n):
    if arr[i] == 1:  # 1 没有质因数，单独成为新序列
        continue
    fac = prime_factors(arr[i])
    if fac:
        cur = max(dp.get(x, 0) for x in fac) + 1
    else:
        cur = 1
    for x in fac:
        dp[x] = cur
    ans = max(ans, cur)

print(ans)

代码解析

prime_factors 函数

• 使用试除法分解质因数
• 返回一个集合（去重）
• 时间复杂度 O(√n)

DP 过程

• dp 字典存储每个质因数当前对应的最长序列长度
• 每次遇到新数，取其所有质因数的最大 dp 值 +1
• 然后将该长度更新到所有相关质因数上

时间复杂度

• 分解质因数：每个数 O(√ai)，总体 O(n × √max(ai))
• DP 更新：O(n × 质因数个数)
• 在实际应用中，由于 ai ≤ 10⁵，质因数个数较少，运行效率较高