Python || Fast & Simple O(N + M sqrt M + Q log M) 🔥
Approach\n1. Group numbers and update frequency only once for each distinct number\n    - Because the max number of disctint values in nums (5 \times 10^4) is p
# Approach\n1. **Group numbers and update frequency only once for each distinct number**\n    - Because the max number of disctint values in `nums` ($$5 \\times 10^4$$) is potentially smaller than the size of `nums` ($$10^5$$) we use a Counter to avoid finding factors for duplicates. \n    - If M is the max value in `nums` this step is $$O(N + M \\sqrt{M})$$.\n    - `freq[g]` = count of numbers that have `g` as a factor.\n\n2. **Number of pairs for each possible GCD using inclusion-exclusion**\n    - `count_gcd[g]` = number of pairs with GCD equal to `g`.\n    - the number of pairs whose GCD could be `g` is:\n     `freq[g] * (freq[g] - 1) // 2`.\n    - For each divisor `g`, the pairs whose GCD is a multiple of `g` (i.e., `2g`, `3g`, `4g`, ...) have also been included and need to be excluded.\n    - The complexity of this step is $$O(M \\log{M})$$, for each `g` we handle `M/g` multiples and $$\\sum_{g=1}^{M} \\frac{1}{g} \\approx \\log M$$).\n\n3. **Process queries using binary search**\n    - We compute the prefix sums for `gcd_count` and use binary search to efficiently solve each query.\n    - The complexity of this step is $$O(Q \\log{Q} + M)$$.\n\n\n# Complexity\n- Time complexity: $$O(N + M \\sqrt{M} + Q \\log{M})$$\n- Space complexity: $$O(M)$$\n(where M is the maximum value of `nums`, Q is the size of `queries`)\n\n# Code\n```python3 []\ndef gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n    max_val = max(nums)\n\n    # Update frequency only once for each distinct number\n    freq = [0] * (max_val + 1)\n    for num, cnt in Counter(nums).items():\n        for g in range(1, int(num**0.5) + 1):\n            if num % g == 0:\n                freq[g] += cnt\n                if g != num // g:\n                    freq[num // g] += cnt\n\n    # Number of pairs for each possible GCD using inclusion-exclusion\n    gcd_count = [0] * (max_val + 1)\n    for g in reversed(range(1, max_val + 1)):\n        if freq[g] > 1:\n            gcd_count[g] = freq[g] * (freq[g] - 1) // 2\n        # Exclude pairs where GCD is a multiple of g\n        for multiple in range(2 * g, max_val + 1, g):\n            gcd_count[g] -= gcd_count[multiple]\n\n    # Process queries\n    gcd_pre = list(accumulate(gcd_count))\n    return [bisect_right(gcd_pre, pos) for pos in queries]\n```
['Python3']