3312. Sorted GCD Pair Queries
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. Find the Maximum Val
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Find the Maximum Value in the Array**:\n        Determine the maximum value from the array `nums[]`. This helps set the upper limit for calculating the GCDs, \n          as no GCD can be larger than the maximum number in the array.\n\n2. **Count Occurrences of Each Element**:\n        Count how many times each element appears in the array. This will be useful when calculating how many pairs have a specific GCD.\n\n3. **Calculate the Number of Pairs for Each Possible GCD**:\n        Loop from 1 to the maximum value (from step 1). For each `i`, do the following:\n             **Find All Numbers Divisible by `i`**: For each number divisible by `i`, count how many such numbers exist in `nums[]`.\n             **Calculate the Number of Pairs with GCD = `i`**: \n               The number of ways to select two numbers with GCD `i` is given by the formula `count * (count - 1) / 2`,\n               where `count` is the number of numbers divisible by `i`.\n             **Overcounting**: While calculating pairs for GCD = `i`, we may also count pairs with higher GCDs (multiples of `i`).\n               For example, while calculating pairs with GCD = 2, we also count pairs with GCD = 4. \n               This overcount will be corrected in the next step.\n\n4. **Correct Overcounting**:\n         Loop backward from the maximum value down to 1. For each i, subtract the extra pairs that were counted for multiples of i. This ensures that pairs with higher GCDs (like 4, 6, etc.) are not mistakenly counted as having a GCD of 2.\n\n5. **Calculate the Prefix Sum**:\n         To efficiently answer the queries, calculate the prefix sum of the GCD pairs. This allows us to determine, for any given query, \n          how many pairs have a GCD less than or equal to a given value.\n\n6. **Answer the Queries**:\n         For each query, use **binary search** on the prefix sum array to find the smallest GCD such that the cumulative number of pairs \n          with that GCD is greater than or equal to the query. Since the GCDs are processed in ascending order, \n          this allows us to efficiently locate the answer for each query.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n\n    public int[] gcdValues(int[] nums, long[] queries) {\n        int max = 1;\n        for (int num : nums) {\n            max = Math.max(max, num);\n        }\n        long[] gcdDp = new long[max + 1];\n        for (int num : nums) {\n            gcdDp[num]++;\n        }\n\n        for (int i = 1; i <= max; i++) {\n            long count = 0;\n            for (int j = i; j <= max; j = j + i) {\n                count += gcdDp[j];\n            }\n            gcdDp[i] = ((count - 1) * count) / 2;\n        }\n\n        for (int i = max; i > 0; i--) {\n            for (int j = i + i; j <= max; j = j + i) {\n                gcdDp[i] -= gcdDp[j];\n            }\n        }\n        for (int i = 1; i <= max; i++) {\n            gcdDp[i] += gcdDp[i - 1];\n        }\n        int[] result = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            result[i] = binarySearch(max, gcdDp, queries[i]+1);\n        }\n        return result;\n    }\n\n    private int binarySearch(int n, long[] arr, long val) {\n        int l = 1;\n        int r = n;\n        while (l < r) {\n            int mid = l + (r - l) / 2;\n            if (arr[mid] < val) {\n                l = mid + 1;\n            } else {\n                r = mid;\n            }\n        }\n        return l;\n    }\n}\n\n```
['Java']