Find the number of subsequences with equal gcd

Array Math Dynamic Programming Number Theory

31.5% acceptance

Feb 23, 2026

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 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn subsequence_pair_count(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let _n = nums.len();
    let max_v = *nums.iter().max().unwrap() as usize;
    
    fn gcd(a: usize, b: usize) -> usize { if b == 0 { a } else { gcd(b, a % b) } }
    
    // dp[g1][g2] = number of ways to assign each element to seq1 (gcd g1), seq2 (gcd g2), or neither
    // For each element, it can go to seq1, seq2, or neither (3 choices, but gcd updates)
    // dp[g1][g2]: g1 = current gcd of seq1 (0 = empty), g2 = current gcd of seq2
    
    let mut dp = vec![vec![0i64; max_v + 1]; max_v + 1];
    dp[0][0] = 1;
    
    for &v in &nums {
      let v = v as usize;
      let mut ndp = vec![vec![0i64; max_v + 1]; max_v + 1];
      for g1 in 0..=max_v {
        for g2 in 0..=max_v {
          if dp[g1][g2] == 0 { continue; }
          let w = dp[g1][g2];
          // Skip v (goes to neither)
          ndp[g1][g2] = (ndp[g1][g2] + w) % MOD;
          // Add v to seq1
          let ng1 = if g1 == 0 { v } else { gcd(g1, v) };
          ndp[ng1][g2] = (ndp[ng1][g2] + w) % MOD;
          // Add v to seq2
          let ng2 = if g2 == 0 { v } else { gcd(g2, v) };
          ndp[g1][ng2] = (ndp[g1][ng2] + w) % MOD;
        }
      }
      dp = ndp;
    }
    
    // Count pairs where g1 == g2 and g1 != 0
    let mut ans = 0i64;
    for g in 1..=max_v {
      ans = (ans + dp[g][g]) % MOD;
    }
    ans as i32
  }
}