1819. Number of Different Subsequences GCDs

Обновлено: 2024-03-12
1 мин
[]

Содержание

LeetCode problem 1819

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        mx = max(nums)
        vis = set(nums)
        res = 0
        for x in range(1, mx + 1):
            g = 0
            for y in range(x, mx + 1, x):
                if y in vis:
                    g = gcd(g, y)
                    if g == x:
                        res += 1
                        break
        return res