[Java] 30ms, Fast GCD precomputation
Intuition\nIf we try to compute GCD for each pair in the array it will TLE.\nNeed to use the GCD values as a base.\n\n# Approach\nWalk over each value in nums, 
# Intuition\nIf we try to compute GCD for each pair in the array it will TLE.\nNeed to use the GCD values as a base.\n\n# Approach\nWalk over each value in nums, check how many nums divisible by `i` we have ahead. We\'re getting all the values having a divisor of `i`. Is it the GCD? Only for those pairs which don\'t have higher GCD.\nNow we traverse the nums back and subtracting the count of pairs which have higher divisors. This way we fill our gcd array.\nNow computing the prefix sums for faster search.\nIn the end going over the queries with binary search.\n\n# Complexity\n- Time complexity:\n$$O(N * log(max(nums)))$$\n\n- Space complexity:\n$$O(max(nums))$$\n\n# Code\n```java []\nclass Solution {\n    public int[] gcdValues(int[] nums, long[] queries) {\n        int max = 0;\n        for (int i : nums) {\n            max = Math.max(max, i);\n        }\n        long[] gcd = new long[max + 1];\n        for (int i : nums) {\n            gcd[i]++;\n        }\n        for (int i = 1; i <= max; i++) {\n            long count = 0;\n            for (int j = i; j <= max; j += i) {\n                count += gcd[j];\n            }\n            gcd[i] = count * (count - 1) / 2;\n        }\n        for (int i = max; i > 0; i--) {\n            for (int j = i + i; j <= max; j += i) {\n                gcd[i] -= gcd[j];\n            }\n        }\n        long[] prefix = new long[max + 1];\n        for (int i = 1; i <= max; i++) {\n            prefix[i] = prefix[i - 1] + gcd[i];\n        }\n        int[] res = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            res[i] = search(prefix, queries[i] + 1);\n        }\n        return res;\n    }\n\n    static int search(long[] arr, long target) {\n        int low = 0;\n        int high = arr.length;\n\n        while (low < high) {\n            int mid = low + (high - low) / 2;\n\n            if (arr[mid] >= target) {\n                high = mid;\n            } else {\n                low = mid + 1;\n            }\n        }\n\n        return low;\n    }\n\n}\n```
['Math', 'Binary Search', 'Prefix Sum', 'Java']