P3245 [HNOI2016] Large Number

Xiao B has a very large number $S$ of length $n$; this number can be regarded as a string of digits and may have leading $0$s, for example, `00009312345`. Xiao B also has a prime $p$. Now, Xiao B proposes $m$ queries. For each query, within a substring of $S$, count how many of its substrings are multiples of $p$ ($0$ is also considered a multiple of $p$). For example, when $S$ is `0077`, its substring `007` has $6$ substrings: `0,0,7,00,07,007`; clearly, all $6$ substrings of `007` are multiples of the prime $7$.

The first line contains an integer $p$. The second line contains a digit string $S$. The third line contains an integer $m$. Then $m$ lines follow, each containing two integers $fr, to$, representing a query on the substring $S[fr\dots to]$ of $S$. Note: the leftmost digit of $S$ has index $1$; for example, if $S$ is `213567`, then $S[1\dots 3]$ is `213`.

Output $m$ lines, each containing one integer. The $i$-th line is the answer to the $i$-th query.

Sample 1 Explanation The first query asks about the entire string. The substrings that satisfy the condition are: `121121,2112,11,121,121`. Constraints For $100\%$ of the testdata, $1\le n,m\le 2\times 10^5$, $2\le p\le 10^9$, $S$ contains only digit characters, and $p$ is prime. Translated by ChatGPT 5