โปรแกรมหาจำนวน GCD ที่แตกต่างของ Subsequence ทั้งหมดใน Python

ปัญหา

กำหนดอาร์เรย์ nums ค่าบวก หาจำนวน GCD ที่แตกต่างกันของทุก Non-empty Subsequence GCD ของลำดับ = ตัวหารร่วมมากที่สุดของทุกตัวในลำดับ

ตัวอย่าง

nums = [4,6,18]

Subsequences: [4]=4, [6]=6, [18]=18, [4,6]=2, [4,18]=2, [6,18]=6, [4,6,18]=2

GCDs ที่แตกต่าง: {2,4,6,18} → 4 ค่า

อัลกอริทึม (Sieve-like)

1. สร้าง Set ของค่าที่ไม่ซ้ำใน nums
2. สำหรับ x = 1 ถึง Max(nums): ตรวจสอบว่า x เป็น GCD ของ subsequence ใดได้หรือไม่
3. วิธีตรวจสอบ: หา GCD ของทุก Multiple ของ x ที่มีอยู่ใน nums (y = x, 2x, 3x, ...)
4. ถ้า GCD ผลลัพธ์ = x → x เป็น GCD ที่เป็นไปได้

ตัวอย่างโค้ด

from math import gcd

def solve(nums):
    T = max(nums) + 1
    nums_set = set(nums)
    ans = 0
    
    for x in range(1, T):
        g = 0
        for y in range(x, T, x):
            if y in nums_set:
                g = gcd(g, y)
            if g == x:
                break
        if g == x:
            ans += 1
    return ans

nums = [4,6,18]
print(solve(nums))  # 4

ความซับซ้อน

• Time: O(M log M) โดย M = max(nums) (Harmonic Series)
• Space: O(M)

เร็วกว่าการ Generate Subsequence ทั้งหมด (2^n) มาก