Sorted GCD Pair Queries

hard Solve on LeetCodeLast edited: July 17, 2026

Problem
Examples
Example 1
Example 2
Example 3
Constraints
Solution
Method 1 - Counting with Möbius Function
Intuition Instead of generating all O(n²) pairs, we count how many pairs have each possible GCD value. We use number theory (Möbius function) to efficiently count pairs with specific GCD values.
Approach
Code
Complexity
Method 2 - Prefix Sum over GCD Counts (No Pair Materialization)
Intuition
Approach
Code
Complexity

चरैवेति चरैवेति | Keep moving on