LeetCode 解題筆記：3336. Find the Number of Subsequences With Equal GCD

作者：王一哲
日期：2026年7月14日


LeetCode 題目連結：3336. Find the Number of Subsequences With Equal GCD

解題想法

困難題。因為 $nums$ 的值範圍不大，只有 1 到 200，可以用動態規畫解題，主要分成 3 個步驟

1. 用字典儲存 dp 資料，key 值為 seq1 的最大公因數 g1 及 seq2 的最大公因數 g2，在 Python 之中 key 值為 tuple 格式，在 C++ 之中則為 pair 格式，預設值為 dp[0, 0] = 1。
2. 依序取出 nums 之中的數字，更新 dp，更新時有 3 種狀況：狀況1，不取 num，不影響 g1, g2；狀況2，取 num 加入 seq1，影響 g1；狀況3，取 num 加入 seq2，影響 g2。
3. 取出 dp 的資料，如果 g1 等於 g2 且 g1 > 0，更新答案 ans。

Python 程式碼

Runtime: 2202 ms, beats 47.73%. Memory: 26.82 MB, beats 36.36%.

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        MOD = 1000000007  # 取餘數用的超大整數
        """
        用字典儲存 dp 資料，key 值為 seq1 的最大公因數 g1 及 seq2 的最大公因數 g2
        key 值為 tuple 格式，預設值為 dp[0, 0] = 1
        """
        dp = defaultdict(int)
        dp[0, 0] = 1

        """ 依序取出 nums 之中的數字，更新 dp """
        for num in nums:
            new_dp = defaultdict(int)  # 新的字典，避免影響到以下的 for 迴圈
            for (g1, g2), val in dp.items():
                # 狀況1，不取 num，不影響 g1, g2
                new_dp[g1, g2] = (new_dp[g1, g2] + val) % MOD
                # 狀況2，取 num 加入 seq1，影響 g1
                new_g1 = gcd(g1, num)
                new_dp[new_g1, g2] = (new_dp[new_g1, g2] + val) % MOD
                # 狀況3，取 num 加入 seq2，影響 g2
                new_g2 = gcd(g2, num)
                new_dp[g1, new_g2] = (new_dp[g1, new_g2] + val) % MOD
            # 交換 dp, new_dp
            dp, new_dp = new_dp, dp
        
        """ 取出 dp 的資料，如果 g1 == g2, g1 > 0，更新答案 ans """
        ans = 0
        for (g1, g2), val in dp.items():
            if g1 == g2 and g1 > 0:
                ans = (ans + val) % MOD
        return ans

C++ 程式碼

Runtime: 2186 ms, beats 5.21%. Memory: 343.66 MB, beats 24.35%.

class Solution {
public:
    int subsequencePairCount(vector<int>& nums) {
        const int MOD = 1000000007;  // 取餘數用的超大整數
        /* 用字典儲存 dp 資料，key 值為 seq1 的最大公因數 g1 及 seq2 的最大公因數 g2
           key 值為 pair 格式，預設值為 dp[0, 0] = 1   */
        map<pair<int, int>, int> dp, new_dp;  // 不能用 unordered_map
        dp[{0, 0}] = 1;

        /* 依序取出 nums 之中的數字，更新 dp */
        for(const auto& num : nums) {
            new_dp.clear();  // 清空字典
            for(const auto& [key, val] : dp) {
                int g1 = key.first, g2 = key.second;
                // 狀況1，不取 num，不影響 g1, g2
                new_dp[{g1, g2}] = (new_dp[{g1, g2}] + val) % MOD;
                // 狀況2，取 num 加入 seq1，影響 g1
                int new_g1 = gcd(g1, num);  // C++ 17 開始於 numeric 函式庫之中提供的工具
                new_dp[{new_g1, g2}] = (new_dp[{new_g1, g2}] + val) % MOD;
                // 狀況3，取 num 加入 seq2，影響 g2
                int new_g2 = gcd(g2, num);
                new_dp[{g1, new_g2}] = (new_dp[{g1, new_g2}] + val) % MOD;
            }
            // 交換 dp, new_dp
            swap(dp, new_dp);
        }
        
        /* 取出 dp 的資料，如果 g1 == g2, g1 > 0，更新答案 ans */
        int ans = 0;
        for(const auto& [key, val] : dp) {
            int g1 = key.first, g2 = key.second;
            if (g1 == g2 && g1 > 0) {
                ans = (ans + val) % MOD;
            }
        }
        return ans;
    }
};