3312. Sorted GCD Pair Queries

#include <stdlib.h>

/*
 * 演算法 / Algorithm:
 * 1) freq[v] 統計每個值出現次數 / count how often each value appears.
 * 2) 對每個 g（由大到小），c=能被 g 整除的元素數，兩數皆整除的數對=c*(c-1)/2，
 *    再用容斥扣掉 exact[2g],exact[3g],… 得到 GCD 恰為 g 的數對數 exact[g].
 * 3) 對 g 做前綴和，二分搜尋回答每個查詢 / prefix-sum then binary search per query.
 */
int* gcdValuesForQueries(int* nums, int numsSize, int* queries,
                         int queriesSize, int* returnSize) {
    int maxV = 0;                                   // 值域上界 / largest value in nums
    for (int i = 0; i < numsSize; i++)              // 掃一遍找最大值 / scan for max
        if (nums[i] > maxV) maxV = nums[i];

    // calloc 配置並清零 / allocate zero-filled array; index = 值, 內容 = 出現次數
    int* freq = calloc(maxV + 1, sizeof(int));      // freq[v] = count of value v
    for (int i = 0; i < numsSize; i++)
        freq[nums[i]]++;                            // 該值出現次數 +1 / bump count

    // 用 long long：數對數可達 ~5e9，超過 int 上限 / pair counts overflow int
    long long* exact = calloc(maxV + 1, sizeof(long long)); // exact[g] = pairs with gcd==g

    for (int g = maxV; g >= 1; g--) {               // 由大到小 / high g first for inclusion-exclusion
        long long c = 0;                            // c = 能被 g 整除的元素個數 / #elements divisible by g
        for (int m = g; m <= maxV; m += g)          // 遍歷 g 的倍數 / walk multiples of g
            c += freq[m];                           // 累加這些值的出現次數 / sum their frequencies
        long long both = c * (c - 1) / 2;           // 兩數皆被 g 整除的數對數 / pairs both divisible by g
        for (int m = 2 * g; m <= maxV; m += g)      // 扣掉 gcd 是 2g,3g,… 的 / remove larger-multiple gcds
            both -= exact[m];                       // 容斥 / inclusion-exclusion subtraction
        exact[g] = both;                            // 剩下的就是 gcd 恰為 g / what remains is gcd exactly g
    }

    // 前綴和：prefix[g] = gcd <= g 的數對總數 / running total of exact counts
    long long* prefix = calloc(maxV + 1, sizeof(long long));
    long long run = 0;                              // 累加器 / running sum
    for (int g = 1; g <= maxV; g++) {               // 由小到大累加 / accumulate ascending
        run += exact[g];
        prefix[g] = run;                            // gcd <= g 的數對數 / pairs with gcd <= g
    }

    int* ans = malloc(queriesSize * sizeof(int));   // 回傳陣列 / output array
    for (int i = 0; i < queriesSize; i++) {
        long long q = queries[i];                   // 查詢的排序索引 / target index in sorted list
        int lo = 1, hi = maxV;                      // 二分搜尋範圍 = 可能的 gcd 值 / search over gcd values
        while (lo < hi) {                           // 找最小 g 使 prefix[g] > q / smallest g with prefix[g] > q
            int mid = lo + (hi - lo) / 2;           // 中點，避免 lo+hi 溢位 / midpoint w/o overflow
            if (prefix[mid] > q) hi = mid;          // 夠大，往左收 / big enough, keep left half
            else lo = mid + 1;                      // 太小，往右找 / too small, go right
        }
        ans[i] = lo;                                // gcdPairs[q] 的值就是 lo / the answer value
    }

    free(freq); free(exact); free(prefix);          // 釋放記憶體避免洩漏 / free to avoid leaks
    *returnSize = queriesSize;                       // 回傳長度 / tell caller the size
    return ans;
}

#include <vector>
using namespace std;

/*
 * 演算法 / Algorithm:
 * 對每個 g 用「兩數皆被 g 整除」的數對數 (c*(c-1)/2)，配合容斥算出 gcd 恰為 g 的數量，
 * 再前綴和 + 二分搜尋回答查詢。/ Count pairs both divisible by g, inclusion-exclusion to get
 * exact-gcd counts, prefix-sum, then binary search per query.
 */
class Solution {
public:
    vector<int> gcdValuesForQueries(vector<int>& nums, vector<int>& queries) {
        // *max_element 回傳最大值的迭代器，解參考取值 / max value in nums
        int maxV = *max_element(nums.begin(), nums.end());

        // vector<int> 自動初始化為 0 / frequency array, index = value
        vector<int> freq(maxV + 1, 0);
        for (int v : nums)                          // range-for：逐一取出元素 / iterate values
            freq[v]++;                              // 該值計數 +1 / count this value

        // long long 防溢位：數對數可達 ~5e9 / avoid int overflow on pair counts
        vector<long long> exact(maxV + 1, 0);       // exact[g] = # pairs with gcd == g
        for (int g = maxV; g >= 1; --g) {           // 由大到小 / descend for inclusion-exclusion
            long long c = 0;                        // # elements divisible by g
            for (int m = g; m <= maxV; m += g)      // g 的倍數 / multiples of g
                c += freq[m];                       // 累加出現次數 / sum frequencies
            long long both = c * (c - 1) / 2;       // 兩數皆整除的數對 / pairs both divisible by g
            for (int m = 2 * g; m <= maxV; m += g)  // 扣掉更大倍數的 gcd / subtract larger-multiple gcds
                both -= exact[m];
            exact[g] = both;                        // gcd 恰為 g / gcd exactly g
        }

        // 前綴和：prefix[g] = gcd <= g 的數對數 / cumulative pair counts
        vector<long long> prefix(maxV + 1, 0);
        long long run = 0;
        for (int g = 1; g <= maxV; ++g)             // 由小到大累加 / accumulate ascending
            prefix[g] = (run += exact[g]);

        vector<int> ans;                            // 結果 / result
        ans.reserve(queries.size());               // 預留空間避免重複配置 / preallocate for speed
        for (long long q : queries) {               // 逐個查詢 / for each query index
            // lower_bound 找第一個 prefix[g] > q 的位置 / first g with prefix[g] > q
            int lo = 1, hi = maxV;                  // 在 gcd 值域上二分 / binary search over gcd values
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;       // 中點 / midpoint
                if (prefix[mid] > q) hi = mid;      // 夠大往左 / enough, shrink right bound
                else lo = mid + 1;                  // 太小往右 / too small, move up
            }
            ans.push_back(lo);                      // 加入答案 / append answer
        }
        return ans;
    }
};