You are given an array \(A = \{ a_0, a_1...a_{N-1} \}\) and an integer D. Find the total number of un-ordered pairs \((i, j)\) where \(i \ne j\) such that \(a_i * a_j \equiv 0 \pmod D\).
INPUT
The first line of each test file contains two space separated integers N and D, where N denotes the size of array A and D is as described above. Next line contains N space separated integers \(a_0 \dotso a_{N-1}\) denoting array A .
OUTPUT
Output a single line containing the number of pairs as described in problem statement.
CONSTRAINTS
- \(1 \le N \le 10^6\)
- \(1 \le D \le 10^6\)
- \(1 \le a_i \le 10^9\)
7 7 2 2 2 7 2 2 1
6
You can take number at index 4 (1 based indexing) with any of other 6 numbers. Their product will be divisible by D i.e. 7. No other pair will give product divisible by D.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor