GCD Pair Queries with Frequency Calculation || Javascript
Intuition\nTo solve the problem of efficiently finding the GCD of all possible pairs in an array and answering queries about these GCD values, we can take advan
# Intuition\nTo solve the problem of efficiently finding the GCD of all possible pairs in an array and answering queries about these GCD values, we can take advantage of the mathematical properties of divisors. Instead of calculating all GCD pairs directly, we use a counting and prefix sum approach to handle the large input sizes.\n\n# Approach\n1. Frequency Count:\n   - For each number in the input nums, we calculate how many times each number occurs and store that in gcdmul.\n\n2. Divisor Pair Counting:\n   - For each possible divisor i, we iterate over all multiples of i and count how many elements in nums are divisible by i. Using this count, we calculate how many pairs of elements have a GCD equal to i.\n\n3. Adjustment:\n   - We then adjust the counts by subtracting the pairs already accounted for by higher divisors to avoid over-counting.\n4. Prefix Sum:\n   - We accumulate the counts of GCD pairs into a prefix sum array qz. This allows us to quickly find how many GCD pairs are smaller than a given value for the queries.\n5. Query Handling:\n   - For each query, we use a binary search to find the smallest GCD pair count that exceeds the query, using the prefix sum array.\n\n# Complexity\n- Time complexity:\n  - Constructing the gcdmul array takes O(n log n) because for each divisor i, we iterate over its multiples.\n  - Each query is answered in O(log n) using binary search. Therefore, for q queries, the total complexity is O(q log n).\n\n- Space complexity:\n  - The space complexity is O(n) due to the storage used for the gcdmul and qz arrays.\n\n# Code\n```javascript []\n/**\n * @param {number[]} nums\n * @param {number[]} queries\n * @return {number[]}\n */\nvar gcdValues = function(nums, queries) {\n    const S = Math.max(...nums) + 1;\n    const gcdmul = new Array(S).fill(0);\n    const qz = new Array(S).fill(0);\n\n    for (let t of nums) {\n        gcdmul[t]++;\n    }\n\n    for (let i = 1; i < S; ++i) {\n        let tt = 0;\n        for (let j = i; j < S; j += i) {\n            tt += gcdmul[j];\n        }\n        gcdmul[i] = Math.floor(tt * (tt - 1) / 2); \n    }\n\n    for (let i = S - 1; i >= 1; --i) {\n        for (let j = i + i; j < S; j += i) {\n            gcdmul[i] -= gcdmul[j];\n        }\n    }\n\n    for (let i = 1; i < S; ++i) {\n        qz[i] = qz[i - 1] + gcdmul[i];\n    }\n\n    const res = [];\n    for (let t of queries) {\n        let index = lowerBound(qz, t + 1);\n        res.push(index);\n    }\n\n    return res;\n};\n\nfunction lowerBound(arr, value) {\n    let low = 1, high = arr.length;\n    while (low < high) {\n        let mid = Math.floor((low + high) / 2);\n        if (arr[mid] < value) low = mid + 1;\n        else high = mid;\n    }\n    return low;\n}\n\n\n```
['JavaScript']