Sorted gcd pair queries

Array Hash Table Math Binary Search Combinatorics Counting Number Theory Prefix Sum

22.3% acceptance

Feb 23, 2026

100

You are given an integer array nums of length n and an integer array queries. Let gcdPairs denote an array obtained by calculating the GCD of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order. For each query queries[i], you need to find the element at index queries[i] in gcdPairs. Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query. The term gcd(a, b) denotes the greatest common divisor of a and b.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn gcd_values(nums: Vec<i32>, queries: Vec<i64>) -> Vec<i32> {
    let max_val = *nums.iter().max().unwrap() as usize;
    // Count frequency of each value
    let mut freq = vec![0i64; max_val + 1];
    for &x in &nums {
      freq[x as usize] += 1;
    }
    // cnt[g] = number of pairs (i,j) where gcd(nums[i],nums[j]) == g
    // First compute: div_cnt[g] = number of pairs where g | gcd(nums[i],nums[j])
    //              = C(count of multiples of g, 2)
    let mut cnt = vec![0i64; max_val + 1];
    for g in 1..=max_val {
      let mut total = 0i64;
      let mut mul = g;
      while mul <= max_val {
        total += freq[mul];
        mul += g;
      }
      cnt[g] = total * (total - 1) / 2;
    }
    // Mobius inversion: exact[g] = cnt[g] - sum(exact[kg] for k>=2)
    for g in (1..=max_val).rev() {
      let mut mul = 2 * g;
      while mul <= max_val {
        let tmp = cnt[mul];
        cnt[g] -= tmp;
        mul += g;
      }
    }
    // Build prefix sums for binary search
    let mut prefix = vec![0i64; max_val + 2];
    for g in 1..=max_val {
      prefix[g] = prefix[g - 1] + cnt[g];
    }
    // Answer queries
    queries.iter().map(|&q| {
      // Find smallest g such that prefix[g] > q
      let mut lo = 1usize;
      let mut hi = max_val;
      while lo < hi {
        let mid = (lo + hi) / 2;
        if prefix[mid] > q {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }
      lo as i32
    }).collect()
  }
}