Leetcode 2183. Count Array Pairs Divisible by K

Count the number of index pairs (i<j) whose product nums[i]*nums[j] is divisible by k. With n up to 1e5, this requires better than O(n^2); a typical solution groups numbers by gcd(nums[i], k) and counts pairs of gcd-values whose product is a multiple of k.