解答：Submission #10651412 - AtCoder Beginner Contest 158
解法：解説AC。
s[i: j]をsのi文字目からj文字目までの部分文字列を評価した整数とする。するとs[i: j] = (s[i: N] - s[j+1: N]) / 10j - i +1であることが重要。つまり、s[i: N]を各iについて保持すると、まとめて計算しやすくなる。
「p ≠ 2 かつ p ≠ 5」の場合はs[i: j] ≡ 0 ⇔ (s[i: N] - s[j+1: N]) ≡ 0である。よって、s[i: N] (mod p)の個数を保持する配列を準備し、iを後ろから見てゆき、事前に保持されたs[i: N] (mod p)の値の個数を解答に加算しつつ、s[i: N] (mod p)の個数を更新してゆけばよい。
上記以外の場合、すなわち「p = 2 または p = 5」の場合は、s[1: k] ≡ s[2: k] ≡ … ≡ s[k: k]である。すなわち下1桁でpで割れるか割れないかが決まるため、下1桁を全てチェックするような実装で済む。
