#3336

Find the Number of Subsequences With Equal GCD

international master · 1950 · lc hard +32 · 31.5% accepted · 88 likes · top 9%

Description

You are given an integer array nums.

Find the number of ordered pairs of non-empty subsequences (seq1, seq2) of nums satisfying both conditions below:

- The subsequences seq1 and seq2 are disjoint: no index of nums is shared between them.

- The GCD of the elements of seq1 equals the GCD of the elements of seq2.

Return the total number of such pairs.

Since the answer may be very large, return it modulo 10⁹ + 7.

Code

1

2

3

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int: