Online Course Discussion Forum

8 Week Usaco Prep Course Assignment 5 Problem 1

 
 
Picture of Dr. Kevin Wang
Re: 8 Week Usaco Prep Course Assignment 5 Problem 1
by Dr. Kevin Wang - Sunday, November 7, 2021, 12:20 AM
 

Let me give an example.  Let's take the string $2019$ itself.  This string contains two substrings that are multiples of $2019$: the whole string $2019$ itself, and the single digit $0$.  We shall use the method described in the homework to verify it.

Consider an invisible leading $0$ as index $0$, and the digit $2$ to be at index $1$, etc., $9$ is at index $4$.  For the array for (1), you get $0$, $2$, $20$, $201$, and $0$ (since $2019 \equiv 0 \pmod{2019}$).  For (2), take the powers of $10$, which are $1$, $10$, $100$, $1000$, $1924$ (since $10000 \equiv 1924\pmod{2019}$).

Then you multiply the results in reverse order: $0\times 1924$, $2\times 1000$, $20\times 100$, $201\times 10$, $0\times 1$, and take each value mod $2019$, and this is the resulting array: $0$, $2000$, $2000$, $2010$, $0$.  There are two pairs of identical values: between indices $0$ and $4$, which gives $2019$; and between indices $1$ and $2$, which gives $0$.  Of course, the original question does not use the digit $0$, but that doesn't really affect the method.

Why does this method work?  This is the mathematical problem that I would like you to figure out by yourself.  It is not hard at all, if you spent some time to think about it.