LeetCode Entry

3312. Sorted GCD Pair Queries

17.07.2026 hard 2026 kotlin rust

Queries of position of gcd of every pair in a sorted order

3312. Sorted GCD Pair Queries hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1423

Problem TLDR

Queries of position of gcd of every pair in a sorted order

Intuition

Didn’t solved

    // 5:30 - have no idea
    //        dp[i] = how many gcds are up to i
    //        sort numbers, 1 2 4 4
    //                          i        ?
    // 8: 00 look for hints: number of pair that have some gcd=g
    //                       again, no idea how
    //       inclusion-exclusion: ?
    // 11:38 gave up

Count number of gcds by computing for each gcd how many multipliers we have. Precompute the multipliers with frequency. Subtract overcounted results of gcd[2a],[3a] and so on. Binary search in a prefix sum of gcds count.

Approach

• computing multipliers in a forward way to find all gcds count is a clever idea

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun gcdValues(n: IntArray, q: LongArray) = run {
        val m = n.max(); val c = IntArray(m+1); for (x in n) ++c[x]; val g = LongArray(m+1)
        for (a in m downTo 1) g[a] = (a..m step a)
            .sumOf{c[it]}.let { 1L*it*(it-1)/2}-(a*2..m step a).sumOf {g[it]}
        for (i in 1..m) g[i] += g[i - 1]
        q.map { v -> g.asList().binarySearch { if (it <= v) -1 else 1 }.inv() }
    }

    pub fn gcd_values(n: Vec<i32>, q: Vec<i64>) -> Vec<i32> {
        let m = *n.iter().max().unwrap() as usize; let mut f = vec![0u64; m + 1];
        let mut g = f.clone(); for n in n { f[n as usize] += 1 };
        for i in (1..=m).rev() {
            let k: u64 = (i..=m).step_by(i).map(|j| f[j]).sum();
            g[i] = k * (k - 1) / 2 - (i * 2..=m).step_by(i).map(|j| g[j]).sum::<u64>();
        }
        for i in 1..=m { g[i] += g[i - 1] }
        q.iter().map(|&x| g.partition_point(|&v| v <= x as u64) as i32).collect()
    }