CF1029D Concatenated Multiples

给定一个由 $n$ 个正整数组成的数组 $a$。 我们定义数字 $x$ 和 $y$ 的“连接”是指将 $x$ 和 $y$ 按顺序拼接在一起所得到的数字。例如，$12$ 和 $3456$ 的连接是 $123456$。 请统计数组 $a$ 中有多少对有序位置对 $(i, j)$（$i \ne j$），使得 $a_i$ 和 $a_j$ 的连接所得的数字能被 $k$ 整除。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^{5}$，$2 \leq k \leq 10^{9}$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{9}$）。

输出一个整数，表示有多少对有序位置对 $(i, j)$（$i \ne j$），使得 $a_i$ 和 $a_j$ 的连接所得的数字能被 $k$ 整除。

在第一个样例中，满足条件的有序对为 $(1,2)$、$(1,3)$、$(2,3)$、$(3,1)$、$(3,4)$、$(4,2)$、$(4,3)$。它们拼接得到的数字分别为 $451$、$4510$、$110$、$1045$、$1012$、$121$、$1210$，这些数字都能被 $11$ 整除。 在第二个样例中，所有 $n(n-1)$ 个有序对都满足条件。 在第三个样例中，没有任何一对满足条件。 由 ChatGPT 4.1 翻译