Sorted GCD Pair Queries

Given nums up to 1e5 elements with values ≤ 5e4, compute how many pairs have each possible gcd value by counting numbers divisible by d and using inclusion–exclusion over multiples (sieve-like subtraction) to get exact pair counts for each gcd, then build cumulative counts and binary-search/map queries to the sorted gcd-pairs array. This avoids enumerating all O(n^2) pairs by leveraging divisor counting and prefix sums.