問題リンク
問題概要
0～9からなる文字列Sと素数Pが与えられる。
Sの連続部分列で、10進数の数とみなした時にPの倍数となるものはいくつあるか。
解法
P=2とP=5は一番下の1桁を見て数えられるので除いておく。
Pが10と互いに素な場合を考える。考え方はZero-Sum RangesやRem of Sum is Numと同じで、先頭からi文字とった時の余りを(累積和的に)管理していけばよい。ただし今回は素朴に差をとっても、桁数の分だけずれている。これに毎回10の累乗を掛けていると間に合わない。
そこで発想を変えて、10の(mod Pでの)逆元を掛ける。たとえば
\(1 → 1 \times 10^{- 1}\)
\(12 → 1 \times 10^{- 1} + 2 \times 10^{- 2}\)
\(123 → 1 \times 10^{- 1} + 2 \times 10^{- 2} + 3 \times 10^{- 3}\)
とすれば、単純に差をとってよくなる。
提出
https://atcoder.jp/contests/abc158/submissions/10607799
感想
下の桁からやればよかったのでは…
