#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;
}