Easy TypeScript Solution | 100% Beats
Intuition\nThe goal of this problem is to efficiently compute the greatest common divisor (GCD) values for given numbers and respond to queries about those GCDs
# Intuition\nThe goal of this problem is to efficiently compute the greatest common divisor (GCD) values for given numbers and respond to queries about those GCDs. By counting the occurrences of each number, we can utilize combinatorial mathematics to calculate how many pairs can be formed that share the same GCD.\n\n# Approach\n1. **Frequency Count**:\n   - Use an array `fr` to keep track of the frequency of each number up to a maximum value of 50,000.\n   - Iterate through `nums` and populate `fr` with the count of each number.\n\n2. **Count Pairs by GCD**:\n   - Initialize an array `ct` to store the count of pairs for each possible GCD.\n   - For each possible GCD `g`, accumulate the frequency of its multiples to calculate how many numbers can share this GCD.\n   - Use the combination formula to count the number of pairs for each GCD.\n\n3. **Adjust Counts for Multiples**:\n   - Iterate from the maximum down to 1, and for each GCD, subtract the counts of its multiples to ensure the counts are exclusive to that GCD.\n\n4. **Prepare for Queries**:\n   - Create two arrays: `xgl` for GCDs with positive counts and `xcl` for their respective counts.\n   - Calculate a prefix sum array `pr` to facilitate quick responses to queries.\n\n5. **Answer Queries**:\n   - For each query, check if it falls within the valid range. If it does, use binary search to find the corresponding GCD.\n\n## Complexity\n- **Time complexity**: \n  - The algorithm runs in \\(O(n + m \\log m + q \\log m)\\), where \\(n\\) is the number of elements in `nums`, \\(m\\) is the maximum number (50,000), and \\(q\\) is the number of queries.\n  \n- **Space complexity**: \n  - The space complexity is \\(O(m)\\) due to the arrays `fr`, `ct`, `xgl`, `xcl`, and `pr`.\n\n# Code\n```typescript []\nfunction gcdValues(nums: number[], queries: number[]): number[] {\n    const mx = 50000;\n    const fr: number[] = new Array(mx + 1).fill(0);\n    nums.forEach(n => {\n        fr[n] += 1;\n    });\n    \n    const ct: number[] = new Array(mx + 1).fill(0);\n    for (let g = 1; g <= mx; g++) {\n    let tm = fr[g] || 0;  // Initialize tm with fr[g]\n    \n    for (let m = g * 2; m <= mx; m += g) {\n        tm += fr[m];\n    }\n    ct[g] = comb(tm, 2);\n}\n\n    \n    for (let g = mx; g >= 1; g--) {\n    const start = 2 * g; \n    for (let m = start; m <= mx; m += g) {\n        ct[g] -= ct[m]; \n    }\n}\n\n    const xgl: number[] = [];\n    const xcl: number[] = [];\n\n    for (let g = 1; g <= mx; g++) {\n        if (ct[g] > 0) {\n            xgl[xgl.length] = g;\n            xcl[xcl.length] = ct[g];\n        }\n}\n\n\n    const szs = xgl.length;\n    const pr: number[] = new Array(szs);\n    pr[0] = xcl[0];\n\n    for (let i = 1; i < szs; i++) {\n        pr[i] = pr[i - 1] + xcl[i];\n    }\n\n    const res: number[] = new Array(queries.length);\n\n    for (let i = 0; i < queries.length; i++) {\n        const q = queries[i];\n        res[i] = (q < 0 || q >= pr[szs - 1]) ? -1 : xgl[binarySearch(pr, q)];\n    }\n\n    return res;\n}\n\nfunction comb(n: number, k: number): number {\n    if (n < k) return 0;\n    \n    const numerator = n * (n - 1);\n    return Math.floor(numerator / 2);\n}\n\n\nfunction binarySearch(pr: number[], q: number): number {\n    let lft = 0, rgt = pr.length - 1;\n    while (lft < rgt) {\n        const m = lft + Math.floor((rgt - lft) / 2);\n        if (pr[m] > q) {\n            rgt = m;\n        } else {\n            lft = m + 1;\n        }\n    }\n    return lft;\n}\n\n```
['TypeScript']