Counting Distinct Ordered Pairs Divisible by k

You are given an array of n integers A and an integer k. Your task is to count the number of ordered pairs (i, j) such that i ≠ j and the product A[i] × A[j] is divisible by k.

In other words, you need to count the number of pairs (i, j) where:

$$A[i] \times A[j] \equiv 0 \; (\text{mod } k)$$

Note: The pairs are considered ordered. For example, if n = 3 and A = [1,2,3] with k = 1, then all 6 distinct ordered pairs (i, j) with i ≠ j are valid.

Examples:

• Input: n = 5, k = 6, A = [1, 2, 3, 4, 5] → Output: 4
• Input: n = 3, k = 10, A = [1, 2, 3] → Output: 0
• Input: n = 1, k = 7, A = [5] → Output: 0

inputFormat

The input is given via standard input (stdin) and has the following format:

 n k
 A[0] A[1] ... A[n-1]

Where:

• n is the number of elements in the array.
• k is the integer that the product of pairs must be divisible by.
• The second line contains n space-separated integers representing the array A.

outputFormat

Output a single integer representing the number of ordered pairs (i, j) (with i ≠ j) such that A[i] × A[j] is divisible by k.

## sample

5 6
1 2 3 4 5

4