Java code ✅
Intuition \n\n1. Count the divisors for each number to understand how many pairs can be formed with a specific GCD.\n2. Start from the maximum value and calcula
# Intuition \n\n1. Count the divisors for each number to understand how many pairs can be formed with a specific GCD.\n2. Start from the maximum value and calculate the number of pairs for each GCD by subtracting counts of multiples to avoid overcounting.\n3. Build a prefix sum of pairs for quick lookups, allowing us to efficiently answer each query using binary search.\n\n# Approach\n1. Count divisors for each number.\n2. Calculate the number of pairs for each GCD from the maximum down to 1.\n3. Build a prefix sum of pairs to quickly answer each query using binary search.\n\n# Complexity\n- Time complexity: $$O(n \\sqrt{m})$$, where $$n$$ is the length of `nums` and $$m$$ is the maximum value in `nums`.\n- Space complexity: $$O(m)$$, where $$m$$ is the maximum value in `nums`.\n\n# Code\n```java\nclass Solution {\n    public int[] gcdValues(int[] nums, long[] queries) {\n        int n = nums.length;\n        int maxValue = Arrays.stream(nums).max().orElse(0);\n        int[] divisorCount = new int[maxValue + 1];\n\n        for (int number : nums) {\n            for (int i = 1; i * i <= number; i++) {\n                if (number % i == 0) {\n                    divisorCount[i]++;\n                    if (i != number / i) {\n                        divisorCount[number / i]++;\n                    }\n                }\n            }\n        }\n\n        long[] gcdPairCount = new long[maxValue + 1];\n\n        for (int gcd = maxValue; gcd >= 1; gcd--) {\n            long count = divisorCount[gcd];\n            gcdPairCount[gcd] = count * (count - 1) / 2;\n            for (int multiple = 2 * gcd; multiple <= maxValue; multiple += gcd) {\n                gcdPairCount[gcd] -= gcdPairCount[multiple];\n            }\n        }\n\n        long[] prefixSum = new long[maxValue + 1];\n        for (int gcd = 1; gcd <= maxValue; gcd++) {\n            prefixSum[gcd] = prefixSum[gcd - 1] + gcdPairCount[gcd];\n        }\n\n        int[] result = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            long query = queries[i];\n            long left = 1, right = maxValue, answer = -1;\n            while (left <= right) {\n                long mid = (left + right) / 2;\n                if (prefixSum[(int) mid] > query) {\n                    answer = mid;\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            result[i] = (int) answer;\n        }\n\n        return result;\n    }\n}\n```\n\n# Upvote if you found this helpful! \uD83D\uDE0A
['Java']