HardRating 2540
1819. Number of Different Subsequences GCDs
arraymathcountingnumber-theory
解題說明
Number of Different Subsequences GCDs
題目描述：給定一個正整數陣列 nums，計算所有非空子序列的 GCD 中有多少個不同的值。
解題思路：不需要枚舉所有子序列（數量指數級）。對於每個候選 GCD 值 g（從 1 到 max(nums)），檢查 nums 中是否存在一個子序列的 GCD 恰好為 g。方法是：找出 nums 中所有 g 的倍數，計算它們的 GCD。若結果恰好等於 g，則 g 是某個子序列的 GCD。因為如果這些倍數的 GCD 為 g，那麼選擇這些數就構成一個 GCD 為 g 的子序列。
C++ 解法
複雜度分析
時間複雜度：O(M × log M) — 其中 M = max(nums)。外層枚舉 g 從 1 到 M，內層枚舉 g 的倍數（調和級數 M/1 + M/2 + ... = O(M log M)），GCD 計算為 O(log M)。
空間複雜度：O(M) — 標記陣列。
虛擬碼
1. Find maxVal = max(nums)
2. Create boolean array present[1..maxVal] marking which values exist
3. For g = 1 to maxVal:
a. curGcd = 0
b. For each multiple of g up to maxVal:
- If present[multiple]: curGcd = gcd(curGcd, multiple)
- If curGcd == g: break early
c. If curGcd == g: count++
4. Return count其他解法
反向篩法：從大到小枚舉 GCD 值，利用已計算的結果避免重複計算。理論上可減少常數，但實作上調和級數遍歷已足夠高效。
因子枚舉法：對每個 nums[i]，枚舉其所有因子並標記。最後檢查哪些因子值確實可作為某子序列的 GCD。時間 O(n × sqrt(M))，在 n 較小時可能更快。
延伸思考
- 若要求的是所有子序列 LCM 的不同值數量，問題的複雜度如何？
- 若 nums 可以動態新增元素，如何即時更新答案？
- 若要輸出每個可能 GCD 值對應的最小子序列，如何修改？