Help in Modular Arithmetic

Правка en1, от MasterMind, 2021-08-09 16:45:41

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:

$$$1817181712114 = 1 \times 10^{12} \mod 2019 + 8 \times 10^{11} \mod 2019 + 1 \times 10^{10} \mod 2019 \dots + 4 \times 10^0 \mod 2019 $$$

and for each residue count how many of the same residue has appeared before, and that will be the answer.

Now reading the editorial:

image

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский MasterMind 2021-08-09 16:45:41 1175 Initial revision (published)