D - Multiple of 2019

D - Multiple of 2019はめちゃくちゃ難しいD問題。

答えは下記のコードとなる。

def solve():

    s = input()
    mod = 2019
    remains = [0]*mod

    ans = 0
    now = 0
    remains[0] = 1
    print(s[::-1])
    # 文字列をreverseし、index付きで走破している
    for i, val in enumerate(s[::-1]):
        print(i, val)
        # 各桁の数値を作る
        now += int(val) * pow(10, i, mod)
        # 2019で割る
        now %= mod
        # 既に存在するmodである場合は足す
        ans += remains[now]
        # modの数を加算
        remains[now] += 1

    print(ans)

if __name__ == "__main__":  
    solve()

数式は今の所深く理解できていないが、要は、2019は2でも5でも割り切れない。 その場合は、各桁をふやしながら2019でわり、出現したあまりを加算していくことで答えになるということだ。