183183

AtCoder

IDabc433_d

Time2000ms

Memory256MB

Difficulty—

For positive integers $x,y$, define $f(x,y)$ as follows: * The value obtained by interpreting $x,y$ in decimal notation without leading zeros as strings, concatenating them in this order to obtain a string $S$, and then interpreting $S$ as an integer in decimal notation. For example, $f(12,3) = 123$ and $f(100,40)=10040$. You are given positive integers $N,M$ and a sequence of $N$ positive integers $A=(A_1,A_2,\ldots,A_N)$. Find the number of pairs of integers $(i,j)$ that satisfy all of the following conditions. * $1\le i,j\le N$ * $f(A_i,A_j)$ is a multiple of $M$. ## Constraints * $1\le N\le 2\times 10^5$ * $1\le M\le 10^9$ * $1\le A_i\le 10^9$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]

Samples

Input #1

2 11
2 42

Output #1

2

*   When $(i,j)=(1,1)$: $f(A_1,A_1)=22$ is a multiple of $11$.
*   When $(i,j)=(1,2)$: $f(A_1,A_2)=242$ is a multiple of $11$.
*   When $(i,j)=(2,1)$: $f(A_2,A_1)=422$ is not a multiple of $11$.
*   When $(i,j)=(2,2)$: $f(A_2,A_2)=4242$ is not a multiple of $11$.

From the above, the pairs of integers that satisfy all the conditions are $(i,j)=(1,1),(1,2)$, which is two pairs. Thus, output $2$.

Input #2

4 7
2 8 16 183

Output #2

Input #3

5 5
1000000000 1000000000 1000000000 1000000000 1000000000

Output #3

Input #4

12 13
80 68 862370 82217 8 56 5 168 672624 6 286057 11864

Output #4

API Response (JSON)

{
  "problem": {
    "name": "183183",
    "description": {
      "content": "For positive integers $x,y$, define $f(x,y)$ as follows: *   The value obtained by interpreting $x,y$ in decimal notation without leading zeros as strings, concatenating them in this order to obtain ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc433_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For positive integers $x,y$, define $f(x,y)$ as follows:\n\n*   The value obtained by interpreting $x,y$ in decimal notation without leading zeros as strings, concatenating them in this order to obtain ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments