c++ solution with explanation
\nFor this question, what we actually care about is the remainder of numbers in nums divided by k rather than numbers themselves. This is because \n    Let\n   
\nFor this question, what we actually care about is the remainder of numbers in nums divided by k rather than numbers themselves. This is because \n    Let\n    num1 = a * k + b, 0 <= b < k , num2 = c * k + d, 0 <= d < k\n    Then\n    num1 * num2 = (a * c) * (k * k) + (a * d + b * c) * k + b * d\n    num1 * num2 % k = b * d % k = (num1 % k) * (num2 % k) % k\n\nAs a result, we should get the remainder for every number in the array, and get the frequency for each remainder.\n\n    unordered_map <long long, long long> res_cnt;\n    for (int num : nums) {\n        res_cnt[num % k]++;\n    }\n\nAfter 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.\n\n    long long ret = 0;\n    for (auto const [num1, count1] : res_cnt) {\n        for (auto const [num2, count2] : res_cnt) {\n            if (num1 < num2) {\n                continue;\n            }\n\n            if (num1 * num2 % k != 0) {\n                continue;\n            }\n\n            if (num1 == num2) {\n                ret += count1 * (count1 - 1) / 2;\n            } else {\n                ret += count1 * count2;\n            }\n        }\n    }\n\nThis solution, however, is not very efficient, with k*k complexity. We need to find alternative solution with reduced complexity.\nFor 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.\nNote among all possible values of num2, there is the smallest one, and we call it num2_min. We can calculate it by \n    num2_min = lcm(num1, k) / num1\nThis is obtained directly from the definition of lcm( Least Common Multiple).\nWe note that all num2 are multiples of num2_min. eg \n    num1 = 4, k = 20, num2_min = 5, num2 = 5,10,15\n    num1 = 12, k = 20, num2_min = 5, num2 = 5,10,15\n\nWe can prove this as follows.\nGiven 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.\nIn that case, we need to iterate only k/num2_min different remainders and calculate number of combinations.\nOf 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.\n\n```\nclass Solution {\n   public:\n    // adding const to signature so that tests are easier to write.\n    long long countPairs(const vector<int>& nums, int k) {\n        unordered_map<long long, long long> res_cnt;\n        for (int num : nums) {\n            res_cnt[num % k]++;\n        }\n \n        long long ret = 0;\n        const long long total_number = nums.size();\n        for (auto const [num1, count1] : res_cnt) {\n            if (num1 == 0) {\n                // numbers in this bucket are already multiple of k,\n                // thus any multiple of these numbers are also multiple of k.\n                // (num1 is multiple of k while num2 is not) + (both num1 and\n                // num2 are multiple of k)\n                ret += count1 * (total_number - count1) +\n                       count1 * (count1 - 1) / 2;\n                continue;\n            }\n \n            // smallest num2 so that num1 * num2 % k == 0, when num1 is fixed\n            const long long num2_min = lcm(num1, (long long)(k)) / num1;\n            for (long long num2 = num2_min; num2 < k; num2 += num2_min) {\n                if (num2 < num1) {\n                    continue;\n                }\n \n                if (num2 == num1) {\n                    ret += count1 * (count1 - 1) / 2;\n                    continue;\n                }\n \n                if (res_cnt.count(num2) == 0) {\n                    continue;\n                }\n \n                ret += count1 * res_cnt.at(num2);\n            }\n        }\n \n        return ret;\n    }\n};\n```
[]