AtCoderBeginnerContest164 D 問題 400 点 「Multiple of 2019」
AtCoderBeginnerContest164 D 問題 400 点 「Multiple of 2019」
問題概要
制約
解法
$i$と$j$をそれぞれ探索していく場合、S の制約が $ 2\times10^5$ なので到底間に合わない。どうにかして短縮する必要がある。 ここで配列の$ a\times{l}$から$ a\times{r}$までを整数として見たものを$ T_{l, r}$ とする。これが 2019 の倍数であるとはすなわち
\[(10^{l-1}a*l + \cdots + 10^{r-1}a*{r}) \% 2019 = 0\]という意味になる。2019 は 10 と互いに素であるので、次が成り立つ
$ (T{l, 0} - T{r-1, 0}) \% 2019 = 0$ $ T{l, 0} \% 2019 = T{r-1, 0} \% 2019$
これより、$ T_{i, 0} \% 2019$をカウントしておいて、各あまりの値から 2 つ選んだ場合の総数を出力すれば良い。 この時、インデックスを簡単にするために文字列 S は右端から見ていく。注目する桁が左にずれるごとに乗数が 1 増加していくが、この時に 2019 と 10 が互いに素なので 2019 で mod をとっていい。これにより整数が大きくなりすぎない。これ思いつかないでしょ…
お気持ち
AC コード
# coding: utf-8
S = input()
ans = 0
P = 2019
N = len(S)
S = S[::-1]
cnt = [0 for _ in range(P)]
cnt[0] = 1
v = 0
bai = 1
for i in range(N):
v = (v + int(S[i]) * bai) % P
bai *= 10
bai %= P
cnt[v] += 1
for i in range(P):
ans += ((cnt[i] - 1) * cnt[i]) // 2
print(ans)