Problem:

Given a string $$$S$$$ containing only digits from $$$1$$$ to $$$9$$$, with length at most $$$5 * 10 ^ 5$$$. Find all pairs $$$(L, R)$$$ such that the substring of $$$S$$$ from $$$L$$$ to $$$R$$$ forms a number divisible by $$$2019$$$.

Problem source (Vietnamese): https://lqdoj.edu.vn/problem/mult2019

My idea for this problem is to try and evaluate all substrings and check if they are divisible, but of course that would be too long. Other than that I am pretty stuck.

I would love to know if there are better ideas for this problem. Thanks in advance!