Java Solution
Complexity\n- Time complexity:O(n*(sqrt(max)))\n Add your time complexity here, e.g. O(n) \n\n# Code\njava-MTL []\n// TEST CASES:- 721/729\nclass Solution {\n\n
# Complexity\n- Time complexity:$$O(n*(sqrt(max)))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java-MTL []\n// TEST CASES:- 721/729\nclass Solution {\n\n    private int gcd(int a, int b) {\n        // edge\n        if (b == 0) {\n            return a;\n        }\n        return gcd(b, a % b);\n    }\n\n    public int[] gcdValues(int[] nums, long[] queries) {\n        int n = nums.length;\n\n        List<Integer> list = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++){\n                list.add(gcd(nums[i], nums[j]));\n            }\n        }\n\n        Collections.sort(list);\n\n        int[] res = new int[queries.length];\n        for (int i = 0; i < res.length; i++) {\n            res[i] = list.get((int) queries[i]);\n        }\n        return res;\n    }\n}\n```\n``` Java-WORKING []\n//WORKING\nclass Solution {\n    public int[] gcdValues(int[] nums, long[] queries) {\n        int n = nums.length;\n\n        int max = Arrays.stream(nums).max().orElse(0);\n        int[] div = new int[max + 1];\n        for (int num : nums) {\n            for (int i = 1; i * i <= num; i++) {\n                if (num % i == 0) {\n                    div[i]++;\n                    if (i != num / i) {\n                        div[num / i]++;\n                    }\n                }\n            }\n        }\n\n        long[] gcd = new long[max + 1];\n        for (int gcd_ = max; gcd_ >= 1; gcd_--) {\n            long cnt = div[gcd_];\n            gcd[gcd_] = cnt * (cnt - 1) / 2;\n            for (int mul = 2 * gcd_; mul <= max; mul += gcd_) {\n                gcd[gcd_] -= gcd[mul];\n            }\n        }\n\n        long[] pref = new long[max + 1];\n        for (int gcd_ = 1; gcd_ <= max; gcd_++) {\n            pref[gcd_] = pref[gcd_ - 1] + gcd[gcd_];\n        }\n\n        int[] res = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            long q = queries[i];\n\n            long left = 1, right = max;\n            long val = -1;\n            while (left <= right) {\n                long mid = (left + right) / 2;\n                if (pref[(int) mid] > q) {\n                    val = mid;\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            res[i] = (int) val;\n        }\n        return res;\n    }\n}\n```
['Array', 'Math', 'Matrix', 'Java']