LeetCode 2183 Count Array Pairs Divisible by K

Problem

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
    nums[i] * nums[j] is divisible by k.

Link

Thought Process

For this question, what we actually care about is the remainder of numbers in nums divided by k rather than numbers themselves. This is because


    Let
    num1 = a * k + b, 0 <= b < k , num2 = c * k + d, 0 <= d < k
    Then
    num1 * num2 = (a * c) * (k * k) + (a * d + b * c) * k + b * d
    num1 * num2 % k = b * d % k = (num1 % k) * (num2 % k) % k

As a result, we should get the remainder for every number in the array, and get the frequency for each remainder.


    unordered_map <long long, long long> res_cnt;
    for (int num : nums) {
        res_cnt[num % k]++;
    }

After that, a brute force solution will be iterating through all the remainder values in two for loops, check whether the product of remainders is a multiple of k. If so, we multiply the frequencies for these two remainders and add it to final results. We only add when remainder in inner loop is greater than or equal to remainder in outer loop for deduplication and if remainders are same, we will use count * (count - 1) / 2 instead of count * count, because we are choosing two elements from same set rather than choosing one element from each set.


    long long ret = 0;
    for (auto const [num1, count1] : res_cnt) {
        for (auto const [num2, count2] : res_cnt) {
            if (num1 < num2) {
                continue;
            }

            if (num1 * num2 % k != 0) {
                continue;
            }

            if (num1 == num2) {
                ret += count1 * (count1 - 1) / 2;
            } else {
                ret += count1 * count2;
            }
        }
    }

This solution, however, is not very efficient, with k*k complexity. We need to find alternative solution with reduced complexity.
For every non-zero remainder num1, we need to find all the non-zero remainders num2, such that num1 * num2 % k == 0. Previously we are iterating through all remainders to find them, which is O(k) complexity for each num1.
Note among all possible values of num2, there is the smallest one, and we call it num2_min. We can calculate it by


    num2_min = lcm(num1, k) / num1

This is obtained directly from the definition of lcm( Least Common Multiple).
We note that all num2 are multiples of num2_min. eg


    num1 = 4, k = 20, num2_min = 5, num2 = 5,10,15
    num1 = 12, k = 20, num2_min = 5, num2 = 5,10,15

We can prove this as follows.
Given num1 * num2_min % k = 0, num1 * num2 % k = 0 let num2 = a * num2_min + b, a,b are integers and 0 <= b < num2_min then num1 * (num2 - a * num2_min) % k = 0 that is num1 * b % k = 0 since num2_min is already the smallest positive integer such that num1 * num2 = 0 and considering b < num2_min we can conclude that b = 0 ! which means any num2 is a multiple of num2_min.
In that case, we need to iterate only k/num2_min different remainders and calculate number of combinations.
Of course, any number, which is already a multiple of k, can be paired with any other number, and the product is still multiple of k. We will also add these pairs to final result.

Code

Test Case