Hello there,
While I was trying to solve the following problem Multiple of 2019
Which is in short: Given a string of digits, Find the number of substrings that are divisible by 2019.
Example: 1817181712114 has $$$3$$$ substrings which are $$$(1, 5)$$$ "18171" , $$$(5, 9)$$$ "18171" , $$$(9, 13)$$$ "12114".
Now the solutions uses prefix sum by transforming the string into:
and for each residue count how many of the same residue has appeared before, and that will be the answer.
Now reading the editorial:
They said, this solution works for 2019 since 2019 is coprime to 10. and It does not work for 2020.
(2020 does not satisfy such conditions, so 2019 is used for this problem)
May I know why it does not work for 2020? and How to solve the same problem assuming that it is 2020.
Thanks