分数: 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