Codeforces 264B Good Sequences：質因數分解動態規劃

題目描述

給定 n 個互不相同的正整數，從中選擇若干個數（可重複選擇）構成嚴格遞增序列，要求相鄰兩數不互質（gcd > 1）。求最長序列長度。

解題思路

1. 排序：因為序列嚴格遞增，等價於從排序後的數組中選擇子序列。
2. 質因數分解：將每個數分解為質因數集合。
3. 狀態定義：`dp[p]` 表示以質因數 `p` 結尾的最長合法序列長度。
4. 轉移方程：對於當前數 `x`，其質因數集合為 `P`。`x` 能接在所有以 `P` 中任一質因數結尾的序列後面。新長度為 `max(dp[p] for p in P) + 1`。隨後更新 `dp[p] = max(dp[p], 新長度)`。

代碼實現 (Java)

import java.util.*;

public class Main {
    static final int N = 100005;
    static int[] prime = new int[N], primeCnt = {0};
    static int[] dp = new int[N]; // dp[質因數] = 最長長度
    static int[] a = new int[N];
    static List factors = new ArrayList<>();

    // 線性篩法預處理質數
    static void initPrime() {
        boolean[] isComp = new boolean[N];
        for (int i = 2; i < N; i++) {
            if (!isComp[i]) prime[primeCnt[0]++] = i;
            for (int j = 0; j < primeCnt[0] && i * prime[j] < N; j++) {
                isComp[i * prime[j]] = true;
                if (i % prime[j] == 0) break;
            }
        }
    }

    // 分解質因數
    static void factorize(int x) {
        factors.clear();
        for (int i = 0; i < primeCnt[0] && prime[i] * prime[i] <= x; i++) {
            if (x % prime[i] == 0) {
                factors.add(prime[i]);
                while (x % prime[i] == 0) x /= prime[i];
            }
        }
        if (x > 1) factors.add(x);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        initPrime();
        int n = in.nextInt();
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        Arrays.sort(a, 0, n);

        int ans = 1;
        for (int i = 0; i < n; i++) {
            factorize(a[i]);
            int mx = 0;
            for (int p : factors) mx = Math.max(mx, dp[p]);
            for (int p : factors) dp[p] = mx + 1;
            ans = Math.max(ans, mx + 1);
        }
        System.out.println(ans);
    }
}

關鍵點

• 利用質因數作為狀態橋樑，避免了 O(n²) 的兩兩 gcd 判斷。
• 線性篩預處理質數，加速分解過程。
• 數組值最大 10^5，質因數個數極少，狀態數可控。