Sum of beautiful subsequences

Array Math Binary Indexed Tree Number Theory

31.3% acceptance

Feb 25, 2026

You are given an integer array nums of length n. For every positive integer g, we define the beauty of g as the product of g and the number of strictly increasing subsequences of nums whose greatest common divisor (GCD) is exactly g. Return the sum of beauty values for all positive integers g. Since the answer could 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 total_beauty(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let max_a = *nums.iter().max().unwrap() as usize;

    // Build a[d] = elements of nums divisible by d, in original order
    let mut a: Vec<Vec<i32>> = vec![vec![]; max_a + 1];
    for &x in &nums {
      let xu = x as usize;
      let mut d = 1usize;
      while d * d <= xu {
        if xu % d == 0 {
          a[d].push(x);
          if d != xu / d {
            a[xu / d].push(x);
          }
        }
        d += 1;
      }
    }

    // For each x, count strictly increasing subsequences of a[x]
    // using a coordinate-compressed BIT
    let mut num_inc = vec![0i64; max_a + 1];
    for x in 1..=max_a {
      if a[x].is_empty() { continue; }
      let seq = &a[x];
      let mut vals: Vec<i32> = seq.clone();
      vals.sort_unstable();
      vals.dedup();
      let m = vals.len();
      let mut bit = vec![0i64; m + 2];
      let mut total = 0i64;
      for &v in seq {
        let r = vals.partition_point(|&u| u < v) + 1; // 1-indexed rank
        // prefix sum [1..r-1]
        let less = {
          let mut s = 0i64;
          let mut idx = r as i32 - 1;
          while idx > 0 {
            s += bit[idx as usize];
            if s >= MOD { s -= MOD; }
            idx -= idx & (-idx);
          }
          s
        };
        let add_here = (less + 1) % MOD;
        // point update at r
        {
          let mut idx = r as i32;
          while idx <= m as i32 {
            bit[idx as usize] += add_here;
            if bit[idx as usize] >= MOD { bit[idx as usize] -= MOD; }
            idx += idx & (-idx);
          }
        }
        total += add_here;
        if total >= MOD { total -= MOD; }
      }
      num_inc[x] = total;
    }

    // Mobius inversion: dp[x] = num_inc[x] - sum dp[y] for y = 2x, 3x, ...
    // gives the count of strictly increasing subsequences with GCD exactly x
    let mut dp = num_inc;
    for x in (1..=max_a).rev() {
      let mut y = x + x;
      while y <= max_a {
        let sub = dp[y];
        dp[x] = (dp[x] - sub + MOD) % MOD;
        y += x;
      }
    }

    let mut ans = 0i64;
    for x in 1..=max_a {
      if dp[x] > 0 {
        ans = (ans + x as i64 * dp[x]) % MOD;
      }
    }
    ans as i32
  }
}