Pythonで毎日AtCoder #51 - Qiita

はじめに 前回 #51 問題 考えたこと 本番では、$i,j$を全探索してTLEしました。計算量は$O((2*10^5)^{2})$となります。この問題の制約だと、$O(N)$くらいに抑えないと通りません。 十進数で表記されている数字は$a_i*10^n+a_{i-1}*10^{n-1} \cdots a_0 * 10^0$と表すことができます。長さ$N$の文字列$S$を右から$i$番目で分けたときの文字列を$S_i$とすると$S_i$は$S_0 + S_1 * 10 ^ 1 \cdots S_i * 10 ^ {N-i}$と表せます。飛び飛びで文字を分けて結合することはできないので、$S$の$i,j,i<j$の区間の文字列$S_{i-j}$は$S_{i-j} = \frac{S_{j}-S_{i}}{10^i}$と書けます。ここで、$2019,10^i$は互いに素(最大公約数が1)です。