P10262 [GESP Sample Level 6] Friendly Substrings

Related multiple-choice and true/false problems: .

You are given a digit string $S$ of length $L$, consisting of digits $0 \sim 9$. It is easy to see that it has $\frac{L(L + 1)}2$ contiguous substrings in total. If the number represented by a substring (leading zeros are allowed) is a multiple of $p$, then this substring is called a “friendly substring” of the digit string $S$ with respect to $p$. For example, if the digit string $S$ is “ $12342$ ” and $p = 2$, then among the $15$ contiguous substrings, the friendly substrings are “ $12$ ”, “ $1234$ ”, “ $12342$ ”, “ $2$ ”, “ $234$ ”, “ $2342$ ”, “ $34$ ”, “ $342$ ”, “ $4$ ”, “ $42$ ”, and “ $2$ ”, for a total of $11$. Note that “ $2$ ” appears $2$ times, but since they occur at different positions in $S$, they are counted as different friendly substrings. Now, given the digit string $S$ and a positive integer $p$, can you compute how many friendly substrings there are?

The first line contains a positive integer $p$. It is guaranteed that $2 \leq p \leq 128$. The second line contains a digit string $S$ of length $L$. It is guaranteed that $1 \leq L \leq 10^6$.

Output one line containing one integer, representing the answer.

# Sample 1 Explanation There are $5$ friendly substrings: $10$, $102$, $0$, $02$, and $2$. Translated by ChatGPT 5