No.315

No.260 の類題である.

$P = 8$ をまず考える.

今回は $A, B$ が大きいので, No.260 と同じようにキーとして何桁目まで見たか, 最大値かどうか, 3が現れたかどうか, 3で割った余り, 8で割った余りを使うと, ループ数が $2 \times 10^6 \times 2 \times 2 \times 3 \times 8 \times 10 = 1.92 \times 10^9$ となってやや間に合わない.

そこで, 8の倍数かどうかは下3桁だけ見ればいいので, 下3桁を除いた部分はキーとして何桁目まで見たか, 最大値かどうか, 3が現れたかどうか, 3で割った余りだけを使って DP を行う. そして最後に下3桁をまとめて処理して8の倍数かどうかで分ける.

$P = 80$ の場合は, 下1桁を除いて $P = 8$ の場合と同様に計算し, 最後に10の倍数かどうかで分ける.

$P = 800$ の場合は, 下2桁を除いて $P = 8$ の場合と同様に計算し, 最後に下2桁をまとめて処理して100の倍数かどうかで分ける.