Cho mảng nums các số dương. Tìm số lượng GCD khác nhau среди tất cả các dãy con (subsequence) không rỗng của nums. GCD của dãy là ước chung lớn nhất chia hết tất cả số trong dãy.
Ví dụ: nums = [4,6,18] → GCDs: 4,6,18,2 → output = 4.
Giải thuật (Sieve-like enumeration)
- T = max(nums) + 1.
- Đặt nums vào set để truy xuất O(1).
- Với mỗi x từ 1 đến T-1: kiểm tra xem x có thể là GCD của một dãy con không.
- Duyệt bội số y của x (y = x, 2x, 3x... < T). Nếu y ∈ nums, cập nhật g = gcd(g, y). Nếu g == x → x là GCD hợp lệ.
Code Python
from math import gcd
def solve(nums):
T = max(nums) + 1
nums = set(nums)
ans = 0
for x in range(1, T):
g = 0
for y in range(x, T, x):
if y in nums:
g = gcd(g, y)
if g == x:
break
if g == x:
ans += 1
return ans
nums = [4, 6, 18]
print(solve(nums)) # 4
Đầu vào / Đầu ra
Input: [4,6,18]
Output: 4