divisible substring - abc 158 e - tac

s = 3543, p = 7 を考える
右から 3, 43, 543, 3543 に対し, 7 で割った余りを持つ

(0), 3, 1, 4, 1 $\ \ \ \ (1)$
0 を埋めた

同じ余り 1 のとこに対応する 2 数を取り出す
43, 3543

3543 - 43 = 3500 で, 7 で割り切れる
同じ余りの数で, 大きい方から小さい方を引いたから

ただ, 答えないといけないのは 3500 でなくて 35 が 7 で割り切れるか

すなわち, 3500 が 7 で割り切れるとき, それを 100 で割っても 7 で割り切れるか

一般に, 100 じゃなくて 10 の冪乗で割ったときに 7 で割り切れるか

ここで, 3500 = 2^2 * 5^3 * 7
で, これが 7 で割り切れる

10 の冪乗, すなわち, 素因数 2, 5 を取り除いても 7 で割り切れることには変わりない

よって, mod をとる p が 2 でも 5 でもなければ, (1) において同じ余りの個数から 2 つ選ぶ組合せの積

s = 3543, p = 2 を考える
右から, 3, 43, 543, 3543

2 で割った余りは,
(0), 1, 1, 1, 1

ここで, 543 - 43 = 500 で 2 で割り切れるが,
見ないといけない数は 500 じゃなくて 5
これは 2 で割り切れない

p と 10 が互いに素でないと, 10 の冪乗で割ったときに p の倍数でなくなることが起こりうる

さて, p = 2 のときは下 1 桁が 2 で割り切れる数,
p = 5 のときは下 1 桁が 0 か 5 の数
を数え上げればいい

p = 2 なら, 自分より右にいくつ 2 で割り切れる数があるかに答えればいい

BIT で解ける