[AtCoder] ABC 164 D – Multiple of 2019

問題

方針

\( 12114 \) は \( 12114 = 2019 \times 6 \) なので \( 2019 \) の倍数です。次に、\( 1211472\) という文字列を考えると、\( 12114 \) という文字列があるので、\( 2019 \) の倍数となる部分文字列があることが分かります。ここで、

\[ 1211400 = 1211472 – 72\]

となるので、\( 121472 \bmod 2019 = 72 \) となることに注目します。

剰余の性質

自然数 \( x \) が  \( x \bmod 2019 = 0\) を満たすとき、自然数 \( y\) を用いて、

\[ 10^{y}x \bmod 2019 = 0 \]

となります。

動的計画法

\( S = s_{n-1}s_{n-2}\cdots s_{0} \) とします。

ここで、\( d(i+1) \) を \( S \) の \( i \) 桁目までの数字 \( s_is_{i-1}\cdots s_0\) の \( 2019 \) の剰余とします。

\[ d(i) = s_is_{i-1}\cdots s_0 \bmod 2019 \]

上記は、

\[ d(i+1) = (d(i) + 10^{i}s_{i}) \bmod 2019\]

と計算できます。ここで、\( d(i) = d(j) (i< j) \) となる \( i, j \) について考えます。\( S = 1211472 \) とすると、\( d(2) = d(7)  = 72 \) となります。したがって、\( d(i) \) の頻度を \( a(d(i)) \) とすると、

\[ \sum_{i=0}^{2018} \dfrac{a(i)(a(i) – 1)}{2}\]

が答えになります。また、\( a(0) \) については、 \( s_{i} \cdots s_{0} \bmod 2019 = 0\) という文字列の個数であり、その部分文字列単体で \( 2019 \) の倍数となるので、\( a(0) = 1 \) と初期化してから頻度を数え上げます。

コード