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!
im interested to know the answer too, pls tell me when u get the answer
I have an idea to solve in $$$O(n2019)$$$. Let's say p[i] is the mod of the number formed by the first i digits. Let's say we moved from i to i+1, then all prefixes before i+1 will multiply by 10, so we can get p[i+1]. Now to find how many substring end up here that satisfy the constraints, we want to find the count of previous prefixes that equal the current prefix. We can keep a frequenxy array and every time we move we loop through it and make f[i*10%2019] = f[i]
Here's an explanation of one possible solution