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 got the answer! It's in the below comments.

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]

That seems interesting, I'll try it

It won't pass since n * 2019 = 1e9 . But I thought that maybe there's an improvement to the solution

Here's an explanation of one possible solution

Why do they use the suffix and not prefix sums?

Define the suffix sum in the following way:

Now, if a substring $$$L, R$$$ is a multiple of 2019, then the value of that substring multiplied by $$$10^i$$$ is still a multiple of 2019 for every $$$i$$$. The reason we use suffix sums is that after calculating $$$s_L - s_{R+1}$$$, we might get a value with zeros at the end, however, we can ignore these since multiplying by any power of 10 doesn't change the divisibility by 2019.

Wait, isn't that the formula for the prefix case instead? In that solution link calculating stuff from the suffix looks much more complicated

And also feel free to check my implementation, I wonder where I got wrong:

Sorry, I've corrected the mistake. The problem in your code is that you don't consider the empty suffix, so initially, you have to set ar[0]=1.

Thanks! I got some tests going down, but for some reason it TLEs.

I'm thinking of some sort of precomputation, because

`p = (p * 10) % 2019`

is pretty expensive. What do you think?Update: the problem is a multitest problem. I definitely feel like I would benefit from a precomputed table.

Update 2: it still TLEs

What is the size of array

`ar`

? It should be`2019`

, so if you made it`100 000`

or something, you waste way too much time for`memset`

.Because beside that the code looks ok to me.

oh, my

`ar`

size is like`10^6`

because I'm lazy to change sizes and stuff. Changed it to 2019 and now it AC'ed.moral of the story don't use memset with comically large arrays.

Thanks!

isnt this is clearly suffix