Formatted question description: https://leetcode.ca/all/2183.html

# 2183. Count Array Pairs Divisible by K (Hard)

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:

• 0 <= i < j <= n - 1 and
• nums[i] * nums[j] is divisible by k.

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation:
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.


Example 2:

Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.


Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 105

Similar Questions:

## Note

k is as large as 1e5. Going over it is slow. We should only go over k’s divisors whose count is at most 128.

83160 and 98280 have the greatest number of diviors, which is 128.

83160 = 11*7*5*3*3*3*2*2*2
98280 = 13*7*5*3*3*3*2*2*2


Maximum number of divisors of any n-digit number. https://oeis.org/A066150

## Solution 1.

// OJ: https://leetcode.com/problems/count-array-pairs-divisible-by-k/

// Time: O(N * log(M, K) + K * sqrt(K)) where M is the max number in A.
// Space: O(K)
// Ref: https://www.hackerearth.com/zh/problem/algorithm/pair-count-5/editorial/
const int maxN = 1e5+1;
int cnt[maxN] = {}, sum[maxN] = {};
class Solution {
public:
long long countPairs(vector<int>& A, int k) {
memset(cnt, 0, (k + 1) * sizeof(int));
vector<int> div; // all the divisors of k
for (int i = 1; i <= k; ++i) {
if (k % i == 0) div.push_back(i);
}
for (int &n : A) {
n = gcd(n, k); // remove factors that k doesn't have. Now A[i] <= k
cnt[n]++;
}
for (int d : div) {
sum[d] = 0;
for (int i = d; i <= k; i += d) {
sum[d] += cnt[i]; // sum[d] is the sum of cnt[i] where i is multiple of d.
}
}
long ans = 0;
for (int n : A) {
int r = k / n;
ans += sum[r];
if (n % r == 0) --ans; // If A[i] is divisible by r, cnt[r] counts A[i] in so we need to minus one.
}
return ans / 2;
}
};


## Solution 2.

Step 1. For each n in A, we only care the gcd(n, k) part of it. So, we convert all n to gcd(n, k).

Step 2. If n * m is divisible by k, then m must be multiple of r = k / gcd(n, k). If we sum cnt[r], cnt[2r], cnt[3r]..., it will get TLE.

// NOTE: This solution gets TLE!
class Solution {
public:
long long countPairs(vector<int>& A, int k) {
int cnt[100001] = {};
long ans = 0;
for (int n : A) {
n = gcd(n, k);
int r = k / n;
for (int i = r; i <= k; i += r) ans += cnt[i]; // This part is inefficient. Lots of i are not divisors of k.
cnt[n]++;
}
return ans;
}
};


It’s because some multiple d of r is not divisor of k (gcd(d, k) != d or k % d != 0), so the count of the multiple is always 0 due to Step 1. We should only focus on those rs that are divisors of k.

// OJ: https://leetcode.com/problems/count-array-pairs-divisible-by-k/

// Time: O(K + N * (log(min(M, K)) + sqrt(K))) where M is the max number in A.
//          It can be reduced to O(log(min(M, K)) + sqrt(K)) if we take O(sqrt(K)) time to compute all the divisors.
// Space: O(K)
class Solution {
public:
long long countPairs(vector<int>& A, int k) {
long long ans = 0;
int cnt[100001] = {};
vector<int> divs; // divs are all the divisors of k. E.g. k = 12, divs = [1,12,2,6,3,4]
for (int i = 1; i <= k; ++i) {
if (k % i == 0) divs.push_back(i);
}
for (int n : A) {
n = gcd(n, k); // n covers gcd(n, k), the other number must cover r = k / gcd(n, k).
int r = k / n;
for (int d : divs) {
if (d % r == 0) ans += cnt[d]; // If d is multiple of k / r, add cnt[d] to answer
}
cnt[n]++;
}
return ans;
}
};


## Solution 3.

// OJ: https://leetcode.com/problems/count-array-pairs-divisible-by-k/

// Time: O(Nlog1e5 + D^2)
// Space: O(D) where D is the number of divisors of k
// Ref: https://leetcode.com/problems/count-array-pairs-divisible-by-k/discuss/1785027/
class Solution {
public:
long long countPairs(vector<int>& A, int k) {
unordered_map<int, int> cnt;
for (int n : A) cnt[gcd(n, k)]++;
long long ans = 0;
for (auto &[a, c1]: cnt) {
for (auto &[b, c2]: cnt) {
if (a <= b && (long)a * b % k == 0) {
ans += a < b ? (long)c1 * c2 : (long)c1 * (c1 - 1) / 2;
}
}
}
return ans;
}
};