## Count Array Pairs Divisible by K

• Time:O(n\sqrt k)
• Space:O(n)

## C++

class Solution {
public:
long long countPairs(vector<int>& nums, int k) {
long long ans = 0;
unordered_map<int, int> gcds;

for (const int num : nums) {
const long long gcd_i = gcd(num, k);
for (const auto& [gcd_j, count] : gcds)
if (gcd_i * gcd_j % k == 0)
ans += count;
++gcds[gcd_i];
}

return ans;
}
};


## JAVA

class Solution {
public long countPairs(int[] nums, int k) {
long ans = 0;
Map<Long, Integer> gcds = new HashMap<>();

for (final int num : nums) {
final long gcd_i = gcd(num, k);
for (final long gcd_j : gcds.keySet())
if (gcd_i * gcd_j % k == 0)
ans += gcds.get(gcd_j);
gcds.merge(gcd_i, 1, Integer::sum);
}

return ans;
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}


## Python

class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
ans = 0
gcds = Counter()

for num in nums:
gcd_i = math.gcd(num, k)
for gcd_j, count in gcds.items():
if gcd_i * gcd_j % k == 0:
ans += count
gcds[gcd_i] += 1

return ans