3312. Sorted GCD Pair Queries

import java.util.*;
class Solution {
    public int[] gcdValues(int[] nums, long[] queries) {
        int max = 0;
        for (int x : nums) max = Math.max(max, x);
        int[] freq = new int[max + 1];
        for (int x : nums) freq[x]++;
        long[] cnt = new long[max + 1];
        for (int g = 1; g <= max; g++) {
            long c = 0;
            for (int j = g; j <= max; j += g) {
                c += freq[j];
            }
            cnt[g] = c * (c - 1) / 2;
        }
        long[] exact = new long[max + 1];
        for (int g = max; g >= 1; g--) {
            exact[g] = cnt[g];
            for (int j = g * 2; j <= max; j += g) {
                exact[g] -= exact[j];
            }
        }
        long[] prefix = new long[max + 1];
        for (int g = 1; g <= max; g++) {
            prefix[g] = prefix[g - 1] + exact[g];
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            long k = queries[i] + 1; // 1-based position
            int l = 1, r = max;
            while (l < r) {
                int mid = (l + r) / 2;
                if (prefix[mid] >= k)
                    r = mid;
                else
                    l = mid + 1;
            }
            ans[i] = l;
        }
        return ans;
    }
}

from typing import List

class Solution:
    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
        mx = max(nums)

        freq = [0] * (mx + 1)
        for x in nums:
            freq[x] += 1

        cnt = [0] * (mx + 1)
        for g in range(1, mx + 1):
            c = 0
            for j in range(g, mx + 1, g):
                c += freq[j]
            cnt[g] = c * (c - 1) // 2

        exact = [0] * (mx + 1)
        for g in range(mx, 0, -1):
            exact[g] = cnt[g]
            for j in range(g * 2, mx + 1, g):
                exact[g] -= exact[j]

        prefix = [0] * (mx + 1)
        for g in range(1, mx + 1):
            prefix[g] = prefix[g - 1] + exact[g]

        ans = []
        for q in queries:
            k = q + 1
            l, r = 1, mx
            while l < r:
                mid = (l + r) // 2
                if prefix[mid] >= k:
                    r = mid
                else:
                    l = mid + 1
            ans.append(l)

        return ans

class Solution {
public:
    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
        int mx = *max_element(nums.begin(), nums.end());

        vector<int> freq(mx + 1);
        for (int x : nums) freq[x]++;

        vector<long long> cnt(mx + 1), exact(mx + 1), prefix(mx + 1);

        for (int g = 1; g <= mx; g++) {
            long long c = 0;
            for (int j = g; j <= mx; j += g)
                c += freq[j];
            cnt[g] = c * (c - 1) / 2;
        }

        for (int g = mx; g >= 1; g--) {
            exact[g] = cnt[g];
            for (int j = g * 2; j <= mx; j += g)
                exact[g] -= exact[j];
        }

        for (int g = 1; g <= mx; g++)
            prefix[g] = prefix[g - 1] + exact[g];

        vector<int> ans;

        for (long long q : queries) {
            long long k = q + 1;
            int l = 1, r = mx;
            while (l < r) {
                int mid = (l + r) / 2;
                if (prefix[mid] >= k)
                    r = mid;
                else
                    l = mid + 1;
            }
            ans.push_back(l);
        }

        return ans;
    }
};

var gcdValues = function(nums, queries) {
    let mx = Math.max(...nums);

    const freq = new Array(mx + 1).fill(0);
    for (const x of nums) freq[x]++;

    const cnt = new Array(mx + 1).fill(0);
    for (let g = 1; g <= mx; g++) {
        let c = 0;
        for (let j = g; j <= mx; j += g)
            c += freq[j];
        cnt[g] = c * (c - 1) / 2;
    }

    const exact = new Array(mx + 1).fill(0);
    for (let g = mx; g >= 1; g--) {
        exact[g] = cnt[g];
        for (let j = g * 2; j <= mx; j += g)
            exact[g] -= exact[j];
    }

    const prefix = new Array(mx + 1).fill(0);
    for (let g = 1; g <= mx; g++)
        prefix[g] = prefix[g - 1] + exact[g];

    const ans = [];

    for (const q of queries) {
        const k = q + 1;
        let l = 1, r = mx;

        while (l < r) {
            const mid = Math.floor((l + r) / 2);
            if (prefix[mid] >= k)
                r = mid;
            else
                l = mid + 1;
        }

        ans.push(l);
    }

    return ans;
};