AT_abc433_d.[ABC433D] 183183

对于正整数 $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$ 的倍数。

输入从标准输入读取，格式如下：

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出满足所有条件的整数对 $(i, j)$ 的个数。

样例解释 1

• 当 $(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$。

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 10^9$
• $1 \le A_i \le 10^9$
• 所有输入值均为整数。

由 ChatGPT 5 翻译