Editorial for Multiple of 2019

Approach

Process the string from right to left.

Let current be the value modulo $2019$ of the suffix we have built so far, and let place be the current power of $10$ modulo $2019$. When we prepend a digit $d$, the new remainder becomes $(current + d \cdot place) \bmod 2019$.

Suppose two suffixes starting at different positions give the same remainder modulo $2019$. Their difference is exactly one substring multiplied by a power of $10$. Since $\gcd(10, 2019) = 1$, multiplication by a power of $10$ is invertible modulo $2019$, so that substring itself must be divisible by $2019$.

Therefore, as we scan from right to left, we only need to count how many times each remainder has appeared before. If the current remainder has already appeared $k$ times, then there are $k$ valid substrings ending at the current position range.

This runs in $O(n)$ time and $O(2019)$ memory.

Solution (Python)

s = input().strip()

counts = [0] * 2019
counts[0] = 1

answer = 0
current = 0
place = 1

for ch in reversed(s):
    current = (current + (ord(ch) - ord("0")) * place) % 2019
    answer += counts[current]
    counts[current] += 1
    place = (place * 10) % 2019

print(answer)