Welcome to Subscribe On Youtube

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.

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.

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.

All Problems

All Solutions