Atcoder Beginner Contest 164 D を Python で解きたい

Question

前提・実現したいこと

この間の ABC164D の問題を今 Python で解いていて，AC コードを書くことができたのですが，一文を付け加えるか否かだけで処理速度がかなり変わり，TLE になってしまいます。どちらも問われる答えを出力するコードであると思うのですが，なぜこの二つのプログラムでこのように処理速度が変わってしまうのでしょうか。具体的には，以下のコードの for ループの一回目の， d %= 2019 になります。

もしかしたら， d %= 2019 を入れなければ WA が返るのかもしれません（提出結果は TLE 以外は AC だったので恐らく正しい答えが返ってくると思われますが）が，その場合でもこの一文を加えないだけで処理速度がこんなにも変化する理由を教えていただきたいです。

TLEコード

s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10

ans = 0

for i in num:
    ans += i*(i-1)//2

print(ans)

ACコード

s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10
    # ここの一文を加える
    d %= 2019

ans = 0

for i in num:
    ans += i*(i-1)//2

print(ans)

Answer 1

Sの長さは最大200000ですから、それくらいの桁数の数値がdに代入されることになります。number絡みの計算でもこの数字は使われます。

絶対値が半端でなく大きい整数の算術演算には困難があります。符号付き64bit整数ですら18桁くらいしか表現できないので（2**63−1という数字になります）、200000桁なんて普通の「整数型」では表せません。

Pythonの場合、32bit環境なら符号付き32bit整数、64bit環境なら符号付き64bit整数でできるだけ表現し、値の範囲をはみ出してしまった場合は多倍長整数型という内部表現を使ってくれるので、とりあえず数値として表現することは可能です。ただし、このフォーマットの数値に対してCPUで効率的に計算を行うことはできません。

要するに、一定以上に絶対値が大きい値の計算はすごく遅いので、dを大きくしないことに重大な意味があると思えば良いと思います。