P8712 [Lanqiao Cup 2020 NOI Qualifier B1] Integer Concatenation

You are given an array $A_1, A_2, \cdots, A_n$ of length $n$. You may choose two numbers $A_i$ and $A_j$ ($i \neq j$), then concatenate $A_i$ and $A_j$ in order to form a new integer. For example, `12` and `345` can be concatenated into `12345` or `34512`. Note that swapping the order of $A_i$ and $A_j$ is always considered as $2$ different ways of concatenation, even when $A_i = A_j$. Please compute how many concatenations result in an integer that is a multiple of $K$.

The first line contains $2$ integers $n$ and $K$. The second line contains $n$ integers $A_1, A_2, \cdots, A_n$.

Output one integer representing the answer.

For all test cases, $1 \le n \le 10^5$, $1 \le k \le 10^5$, and $1 \le A_i \le 10^9$. Lanqiao Cup 2020, First Round Provincial Contest, Group B, Problem I. Translated by ChatGPT 5