Олимпиадный тренинг

Задача . D. Склеенные множители


Задан массив \(a\), состоящий из \(n\) положительных целых чисел.

Назовем конкатенацией чисел \(x\) и \(y\) такое число, что оно получается при записывании чисел \(x\) и \(y\) подряд без изменения порядка. Например, конкатенация чисел \(12\) и \(3456\) — это число \(123456\).

Посчитайте количество упорядоченных пар позиций \((i, j)\) (\(i \neq j\)) в массиве \(a\) таких, что конкатенация \(a_i\) и \(a_j\) делится на \(k\).

Входные данные

В первой строке записаны два целых числа \(n\) и \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(2 \le k \le 10^9\)).

Во второй строке записаны \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

Выходные данные

Выведите одно целое число — количество упорядоченных пар позиций \((i, j)\) (\(i \neq j\)) в массиве \(a\) таких, что конкатенация \(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)\) пар подходят.

В третьем примере ни одна пара не подходит.


Примеры
№Входные данныеВыходные данные
1
6 11
45 1 10 12 11 7
7
2
4 2
2 78 4 10
12
3
5 2
3 7 19 3 3
0
Статистика успешных решений по компиляторам
 Кол-во
С++5