HardRating 2246

2183. Count Array Pairs Divisible by K

arrayhash-tablemathcountingnumber-theory

解題說明

Count Array Pairs Divisible by K

題目描述：給定一個整數陣列 nums 和整數 k，計算有多少對 (i, j)（i < j）滿足 nums[i] * nums[j] 能被 k 整除。

解題思路： nums[i] * nums[j] 被 k 整除，等價於 gcd(nums[i], k) * gcd(nums[j], k) 的乘積能被 k 整除。更精確地說，令 gi = gcd(nums[i], k)，則需要 gi * gj % k == 0。

對每個元素計算其與 k 的 GCD。由於 GCD 值必為 k 的因數，種類數量有限（最多 O(√k) 個因數）。
用 hash map 統計每個 GCD 值出現的次數。
枚舉所有 GCD 值的配對 (g1, g2)，若 g1 * g2 % k == 0，則加入 count[g1] * count[g2] 對。注意 g1 == g2 時的配對數為 C(count, 2)。

這樣枚舉 k 的因數對，數量遠小於 n^2。

C++ 解法

複雜度分析

時間複雜度：O(n + d^2) — 計算所有 GCD 為 O(n)，枚舉因數對為 O(d^2)，其中 d 為 k 的因數個數。由於 d = O(√k)，d^2 = O(k)，通常遠小於 n。

空間複雜度：O(d) — hash map 最多存 d 個不同的 GCD 值。

虛擬碼

1. For each nums[i], compute g = gcd(nums[i], k). Count occurrences in a map.
2. For each pair of distinct GCD values (g1, g2) where g1 <= g2:
   a. If g1 * g2 % k == 0:
      - If g1 == g2: ans += count[g1] * (count[g1] - 1) / 2.
      - Else: ans += count[g1] * count[g2].
3. Return ans.

其他解法

逐元素計算法：對每個元素 nums[i]，計算需要配對的 GCD 條件 need = k / gcd(nums[i], k)，然後在已處理的元素中查找 gcd(nums[j], k) 是 need 的倍數的數量。時間複雜度 O(n * d)，每個元素只需查詢 d 個可能的因數。
暴力枚舉：直接枚舉所有 i < j 對，檢查 nums[i] * nums[j] % k == 0。時間複雜度 O(n^2)，只適用於小規模輸入。

延伸思考

若要找三元組 (i, j, k) 使得 nums[i] * nums[j] * nums[k] 被 K 整除，GCD 分組法如何擴展？
若 k 非常大（如 10^18），GCD 計算和因數枚舉的效率如何保證？
若陣列支援動態插入/刪除元素，如何維護配對計數？

Count Array Pairs Divisible by K — CaffeCode