Find the Number of Subsequences With Equal GCD

Problem

You are given an integer array nums.

Your task is to find the number of pairs of non-empty subsequences (seq1, seq2) of nums that satisfy the following conditions:

The subsequences seq1 and seq2 are disjoint , meaning no index of nums is common between them.
The GCD of the elements of seq1 is equal to 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^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19



Input: nums = [1,2,3,4]

Output: 10

Explanation:

The subsequence pairs which have the GCD of their elements equal to 1 are:

  * `([**_1_** , 2, 3, 4], [1, **_2_** , **_3_** , 4])`
  * `([**_1_** , 2, 3, 4], [1, **_2_** , **_3_** , **_4_**])`
  * `([**_1_** , 2, 3, 4], [1, 2, **_3_** , **_4_**])`
  * `([**_1_** , **_2_** , 3, 4], [1, 2, **_3_** , **_4_**])`
  * `([**_1_** , 2, 3, **_4_**], [1, **_2_** , **_3_** , 4])`
  * `([1, **_2_** , **_3_** , 4], [**_1_** , 2, 3, 4])`
  * `([1, **_2_** , **_3_** , 4], [**_1_** , 2, 3, **_4_**])`
  * `([1, **_2_** , **_3_** , **_4_**], [**_1_** , 2, 3, 4])`
  * `([1, 2, **_3_** , **_4_**], [**_1_** , 2, 3, 4])`
  * `([1, 2, **_3_** , **_4_**], [**_1_** , **_2_** , 3, 4])`

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11



Input: nums = [10,20,30]

Output: 2

Explanation:

The subsequence pairs which have the GCD of their elements equal to 10 are:

  * `([**_10_** , 20, 30], [10, **_20_** , **_30_**])`
  * `([10, **_20_** , **_30_**], [**_10_** , 20, 30])`

Example 3

1
2
3
4



Input: nums = [1,1,1,1]

Output: 50

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 200

Solution

Method 1 – Inclusion-Exclusion with GCD Counting

Intuition

For each possible GCD value, count the number of subsequences whose GCD is exactly that value. For each such group, the number of ways to pick two disjoint non-empty subsequences is (2^cnt - 1)^2 - (2^{cnt} - 1), where cnt is the number of elements divisible by the GCD. We use inclusion-exclusion to avoid overcounting subsequences with GCDs that are multiples of the current value.

Approach

Count the frequency of each number in nums.
For each possible GCD g from max(nums) down to 1:
- Count how many numbers in nums are divisible by g (call this cnt).
- The total number of non-empty subsequences of these cnt numbers is 2^cnt - 1.
- Use inclusion-exclusion: subtract the counts for all multiples of g greater than g.
- Store the number of subsequences with GCD exactly g.
For each g, the number of valid pairs is f[g] * (f[g] - 1), where f[g] is the number of non-empty subsequences with GCD g.
Sum over all g and return the result modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
    int numberOfSubsequences(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int mx = *max_element(nums.begin(), nums.end());
        vector<int> cnt(mx + 1);
        for (int x : nums) cnt[x]++;
        vector<int> f(mx + 1);
        vector<int> pow2(nums.size() + 1, 1);
        for (int i = 1; i <= nums.size(); ++i) pow2[i] = (pow2[i-1] * 2LL) % MOD;
        for (int g = mx; g >= 1; --g) {
            int c = 0;
            for (int k = g; k <= mx; k += g) c += cnt[k];
            if (c == 0) continue;
            long long total = (pow2[c] - 1 + MOD) % MOD;
            for (int k = 2 * g; k <= mx; k += g) total = (total - f[k] + MOD) % MOD;
            f[g] = total;
        }
        long long ans = 0;
        for (int g = 1; g <= mx; ++g) {
            if (f[g] >= 2) ans = (ans + f[g] * (f[g] - 1LL)) % MOD;
        }
        return (int)ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


func numberOfSubsequences(nums []int) int {
    mod := int(1e9 + 7)
    mx := 0
    for _, x := range nums {
        if x > mx {
            mx = x
        }
    }
    cnt := make([]int, mx+1)
    for _, x := range nums {
        cnt[x]++
    }
    f := make([]int, mx+1)
    pow2 := make([]int, len(nums)+1)
    pow2[0] = 1
    for i := 1; i <= len(nums); i++ {
        pow2[i] = pow2[i-1] * 2 % mod
    }
    for g := mx; g >= 1; g-- {
        c := 0
        for k := g; k <= mx; k += g {
            c += cnt[k]
        }
        if c == 0 {
            continue
        }
        total := (pow2[c] - 1 + mod) % mod
        for k := 2 * g; k <= mx; k += g {
            total = (total - f[k] + mod) % mod
        }
        f[g] = total
    }
    ans := 0
    for g := 1; g <= mx; g++ {
        if f[g] >= 2 {
            ans = (ans + f[g]*(f[g]-1)) % mod
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    public int numberOfSubsequences(int[] nums) {
        int MOD = 1_000_000_007;
        int mx = 0;
        for (int x : nums) mx = Math.max(mx, x);
        int[] cnt = new int[mx + 1];
        for (int x : nums) cnt[x]++;
        int[] f = new int[mx + 1];
        int[] pow2 = new int[nums.length + 1];
        pow2[0] = 1;
        for (int i = 1; i <= nums.length; ++i) pow2[i] = (int)((pow2[i-1] * 2L) % MOD);
        for (int g = mx; g >= 1; --g) {
            int c = 0;
            for (int k = g; k <= mx; k += g) c += cnt[k];
            if (c == 0) continue;
            long total = (pow2[c] - 1 + MOD) % MOD;
            for (int k = 2 * g; k <= mx; k += g) total = (total - f[k] + MOD) % MOD;
            f[g] = (int)total;
        }
        long ans = 0;
        for (int g = 1; g <= mx; ++g) {
            if (f[g] >= 2) ans = (ans + f[g] * (long)(f[g] - 1)) % MOD;
        }
        return (int)ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    fun numberOfSubsequences(nums: IntArray): Int {
        val MOD = 1_000_000_007
        val mx = nums.maxOrNull() ?: 0
        val cnt = IntArray(mx + 1)
        for (x in nums) cnt[x]++
        val f = IntArray(mx + 1)
        val pow2 = IntArray(nums.size + 1) { 1 }
        for (i in 1..nums.size) pow2[i] = (pow2[i-1] * 2L % MOD).toInt()
        for (g in mx downTo 1) {
            var c = 0
            for (k in g..mx step g) c += cnt[k]
            if (c == 0) continue
            var total = (pow2[c] - 1 + MOD) % MOD
            for (k in 2 * g..mx step g) total = (total - f[k] + MOD) % MOD
            f[g] = total
        }
        var ans = 0L
        for (g in 1..mx) {
            if (f[g] >= 2) ans = (ans + f[g].toLong() * (f[g] - 1)) % MOD
        }
        return ans.toInt()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def numberOfSubsequences(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        mx = max(nums)
        cnt = [0] * (mx + 1)
        for x in nums:
            cnt[x] += 1
        f = [0] * (mx + 1)
        pow2 = [1] * (len(nums) + 1)
        for i in range(1, len(nums) + 1):
            pow2[i] = pow2[i-1] * 2 % MOD
        for g in range(mx, 0, -1):
            c = sum(cnt[k] for k in range(g, mx+1, g))
            if c == 0:
                continue
            total = (pow2[c] - 1) % MOD
            for k in range(2*g, mx+1, g):
                total = (total - f[k]) % MOD
            f[g] = total
        ans = 0
        for g in range(1, mx+1):
            if f[g] >= 2:
                ans = (ans + f[g] * (f[g] - 1)) % MOD
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


impl Solution {
    pub fn number_of_subsequences(nums: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mx = *nums.iter().max().unwrap() as usize;
        let mut cnt = vec![0; mx + 1];
        for &x in &nums { cnt[x as usize] += 1; }
        let mut f = vec![0i64; mx + 1];
        let mut pow2 = vec![1i64; nums.len() + 1];
        for i in 1..=nums.len() {
            pow2[i] = pow2[i-1] * 2 % MOD;
        }
        for g in (1..=mx).rev() {
            let mut c = 0;
            let mut k = g;
            while k <= mx {
                c += cnt[k];
                k += g;
            }
            if c == 0 { continue; }
            let mut total = (pow2[c] - 1 + MOD) % MOD;
            let mut k = 2 * g;
            while k <= mx {
                total = (total - f[k] + MOD) % MOD;
                k += g;
            }
            f[g] = total;
        }
        let mut ans = 0i64;
        for g in 1..=mx {
            if f[g] >= 2 {
                ans = (ans + f[g] * (f[g] - 1) % MOD) % MOD;
            }
        }
        ans as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    numberOfSubsequences(nums: number[]): number {
        const MOD = 1e9 + 7;
        const mx = Math.max(...nums);
        const cnt = Array(mx + 1).fill(0);
        for (const x of nums) cnt[x]++;
        const f = Array(mx + 1).fill(0);
        const pow2 = Array(nums.length + 1).fill(1);
        for (let i = 1; i <= nums.length; ++i) pow2[i] = pow2[i-1] * 2 % MOD;
        for (let g = mx; g >= 1; --g) {
            let c = 0;
            for (let k = g; k <= mx; k += g) c += cnt[k];
            if (c === 0) continue;
            let total = (pow2[c] - 1 + MOD) % MOD;
            for (let k = 2 * g; k <= mx; k += g) total = (total - f[k] + MOD) % MOD;
            f[g] = total;
        }
        let ans = 0;
        for (let g = 1; g <= mx; ++g) {
            if (f[g] >= 2) ans = (ans + f[g] * (f[g] - 1)) % MOD;
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(N log M) — For each divisor, we process all multiples, where N is the length of nums and M is the max value in nums.
🧺 Space complexity: O(M) — For the count and DP arrays, where M is the max value in nums.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Inclusion-Exclusion with GCD Counting#

Intuition#

Approach#

Code#

Complexity#