You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k.
A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k (0 <= i <= n - 1, 0 <= j <= m - 1).
Return the total number of good pairs.
Example 1:
Input:nums1 = [1,3,4], nums2 = [1,3,4], k = 1
Output:5
Explanation:
The 5 good pairs are (0, 0), (1, 0), (1, 1), (2, 0), and (2, 2).
Example 2:
Input:nums1 = [1,2,4,12], nums2 = [2,4], k = 3
Output:2
Explanation:
The 2 good pairs are (3, 0) and (3, 1).
Constraints:
1 <= n, m <= 105
1 <= nums1[i], nums2[j] <= 106
1 <= k <= 103
Solutions
Solution 1: Hash Table + Enumerate Multiples
We use a hash table cnt1 to record the occurrence times of each number divided by $k$ in array nums1, and a hash table cnt2 to record the occurrence times of each number in array nums2.
Next, we enumerate each number $x$ in array nums2. For each number $x$, we enumerate its multiples $y$, where the range of $y$ is $[x, \textit{mx}]$, where mx is the maximum key value in cnt1. Then we count the sum of cnt1[y], denoted as $s$. Finally, we add $s \times v$ to the answer, where $v$ is cnt2[x].
The time complexity is $O(n + m + (M / k) \times \log m)$, and the space complexity is $O(n + m)$. Where $n$ and $m$ are the lengths of arrays nums1 and nums2 respectively, and $M$ is the maximum value in array nums1.