← 返回题目列表

AtCoder · abc433_d

G. 183183数字

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

对于正整数 x,y,定义 f(x,y) 如下:

  • 解释得到的值 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

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