MasterMind's blog

Help in Modular Arithmetic

By MasterMind, history, 3 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does it not work for 2020? Look at how it works for 2019. The key idea is that a substring, say 1817 18171 2114 is divisible by 2019 if and only if 181710000 is. Which is true. An integer $$$n$$$ is divisible by 2019 if and only if $$$10^kn$$$ is, because 10 and 2019 are coprime. On the contrary, take the string 120213. Your algorithm would find 1 202 13 as a number divisible by 2020 because 20200 is divisible by 2020. So, how to solve this issue? Notice that a number is divisible by 2020 if and only if it is divisible by 101 and 20. (In general, use the prime factor decomposition $$$n=2^a5^b\cdot k$$$.) So, check both divisibility by 101 (using prefix sums) and by 20 (last digit 0, second-to-last digit even) seperately.

→ Reply