Codeforces Round #506 (Div. 3)D. Concatenated Multiples

問題概要

数字 $x$ と $y$ の連結を, 文字列として $x$ と $y$ を連結したときにできる数とする. たとえば $12$ と $3456$ の連結は $123456$ である.

長さ $n$ の数列 $a_n$ と $k$ が与えられる. このうち, $a_i$ と $a_j$ ( $i \neq j$ ) の連結が $k$ で割り切れるような順序付きペア $(i, j)$ の個数を求めよ.

制約

$1 \le n \le 2\times 10^5$
$1 \le k \le 10^9$
$1 \le a_i \le 10^9$

解法

$a_i$ と $a_j$ の連結が $k$ で割り切れるには, $a_j$ の桁数を $p_j$ として $(a_i\times 10^{p_j} + a_j) \equiv 0~\mathrm{mod}~k$ が満たされている必要があります. これを数え上げることにしましょう.

$a_i$ を固定したとき, $a_i \times 10^{p_j} \equiv -a_j$ を満たすものを数えます. 左辺に $j$ に依存する値が入っていて厄介ですが, $p_j$ は高々 $10$ 通りの値しかとらないので, (桁数が $t$ で, $k$ で割った余りが $s$ ) の個数をあらかじめ計算しておけば数え上げることができます( $-a_j$ を数え上げるのに注意してください).