D - 183183 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

正整数 x,y に対して f(x,y) を以下のように定義します。

  • 先頭に余分な 0 を付けない十進表記の x,y をそれぞれ文字列として解釈しこの順に連結して得られる文字列を S としたときの、 S を十進表記の整数として解釈した値。

例えば f(12,3) = 123 、f(100,40)=10040 です。

正整数 N,M と長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

以下の条件を全て満たす整数の組 (i,j) の個数を求めてください。

  • 1\le i,j\le N
  • f(A_i,A_j) は M の倍数

制約

  • 1\le N\le 2\times 10^5
  • 1\le M\le 10^9
  • 1\le A_i\le 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \ldots A_N

出力

条件を全て満たす整数の組 (i,j) の個数を出力せよ。

入力例 1

2 11
2 42

出力例 1

2
  • (i,j)=(1,1) のとき： f(A_1,A_1)=22 は 11 の倍数です。
  • (i,j)=(1,2) のとき： f(A_1,A_2)=242 は 11 の倍数です。
  • (i,j)=(2,1) のとき： f(A_2,A_1)=422 は 11 の倍数ではありません。
  • (i,j)=(2,2) のとき： f(A_2,A_2)=4242 は 11 の倍数ではありません。

以上より、条件を全て満たす整数の組は (i,j)=(1,1),(1,2) の 2 つです。したがって、 2 を出力してください。

入力例 2

4 7
2 8 16 183

出力例 2

4

入力例 3

5 5
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

25

入力例 4

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

出力例 4

10

Score : 400 points

Problem Statement

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

Output

Output the number of pairs of integers (i,j) that satisfy all the conditions.

Sample Input 1

2 11
2 42

Sample 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.

Sample Input 2

4 7
2 8 16 183

Sample Output 2

4

Sample Input 3

5 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

25

Sample Input 4

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

Sample Output 4

10