Online Course Discussion Forum
8 Week Usaco Prep Course Assignment 5 Problem 1
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.
社交网络