Competitive ProgrammingNumber TheorySegment Tree

LeetCode Weekly Contest 497 Q4 Good Subsequence Queries

2026-04-12

問題重述

給你一個陣列 nums（長度 $n$ ）、整數 $p$ 、一堆更新 queries。

每次 query 改一個元素之後問：

能不能從 nums 裡面挑一些元素（不能全選），讓 GCD 剛好等於 $p$ ？

回傳能的 query 數量。

Step 1：轉化

GCD 剛好等於 $p$ 其實就是：

選的元素全部被 $p$ 整除
除以 $p$ 之後 GCD = 1

設 $\text{val}[i] = \text{nums}[i] / p$ （不整除就設 0）， $\text{tot}$ = 非零 val 的個數， $g = \gcd(\text{所有 val})$ 。

問題就變成：vals 裡面有沒有大小 1 到 n-1 的子集 GCD = 1？

Step 2：五個 Case

Case	條件	結論	原因
1	$\text{tot} = 0$	NO	沒有 $p$ 的倍數
2	$g > 1$	NO	任何子集 $\gcd \ge g > 1$
3	$g = 1,\ \text{tot} < n$	YES	全選非零 vals，長度 $\text{tot} < n$
4	$g = 1,\ \text{tot} = n,\ \exists\, \text{val} = 1$	YES	單選 val=1 的元素，長度 1
5	$g = 1,\ \text{tot} = n,\ \text{no val} = 1$	要檢查	全選長度 = n 不合法

Step 3：Case 5 的處理

剩下的 case：所有 val 都 > 1、沒有 val = 1、整體 GCD = 1。能不能拿掉一個讓 GCD 還是 1？

有重複的 val 就直接 YES，同一個值不可能只有一個缺席。要相異的話最多 6 個（質數連乘長很快，7 個就超題目值域了），直接暴力枚舉算去掉一個的 GCD 就好。

實作上用 Segment Tree 維護全局 GCD，再另外動態記 tot（ $p$ 的倍數數量）跟 c1（val = 1 的數量），這樣前面幾個 case 都能 $O(1)$ 判掉。每次 query $O(\log n)$ ，總共 $O(q \cdot \log n)$ 。

完整 Code

cpp

class Solution {
public:
    vector<int> val;
    vector<int> tree;

    void build(int x, int l, int r) {
        if (l == r) {
            tree[x] = val[l];
            return;
        }
        int mid = (l + r) / 2;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        tree[x] = __gcd(tree[x << 1], tree[x << 1 | 1]);
    }

    void update(int x, int l, int r, int idx) {
        if (l == r) {
            tree[x] = val[idx];
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) {
            update(x << 1, l, mid, idx);
        } else {
            update(x << 1 | 1, mid + 1, r, idx);
        }
        tree[x] = __gcd(tree[x << 1], tree[x << 1 | 1]);
    }

    int countGoodSubseq(vector<int>& nums, int p, vector<vector<int>>& q) {
        int n = nums.size();
        val.resize(n + 5);
        tree.resize(n * 4 + 50);
        int c1 = 0;
        int tot = 0;

        for (int i = 0; i < n; i++) {
            if (nums[i] % p != 0) {
                val[i] = 0;
            } else {
                val[i] = nums[i] / p;
                if (val[i] == 1) c1++;
                tot++;
            }
        }
        build(1, 0, n - 1);

        int ans = 0;
        for (auto& i : q) {
            int idx = i[0];
            int v = i[1];

            // 更新計數器
            if (val[idx] > 0) tot--;
            if (val[idx] == 1) c1--;

            if (v % p) {
                v = 0;
            } else {
                v /= p;
            }
            val[idx] = v;

            if (val[idx] > 0) tot++;
            if (val[idx] == 1) c1++;

            update(1, 0, n - 1, idx);

            // Case 2: 整體 GCD > 1
            int Gcd = tree[1];
            if (Gcd != 1) continue;

            // Case 1: 沒有 p 的倍數
            if (tot == 0) continue;

            // Case 3: 不是全部都是 p 的倍數
            if (tot < n) {
                ans++;
            }
            // Case 4: 有 val = 1 的元素
            else if (c1) {
                ans++;
            }
            // Case 5, n >= 7: 質數連乘超值域
            else if (n >= 7) {
                ans++;
            }
            // Case 5, n <= 6: 暴力枚舉
            else {
                for (int i = 0; i < n; i++) {
                    int g = 0;
                    for (int j = 0; j < n; j++) {
                        if (j != i) {
                            g = __gcd(g, val[j]);
                        }
                    }
                    if (g == 1) {
                        ans++;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

解法 Flow

\gcd = p

→ 除以

p

變成子集

\gcd = 1

↓

Segment Tree 維護 GCD，tot / c1 快速判 Case 1-4

↓

Case 5：質數連乘長很快 →

n \ge 7

直接 YES

↓

n \le 6

：暴力

O(n^2)

LeetCodeSegment TreeGCDNumber TheoryCompetitive Programming