A5714. 「HNOI2016」大数
编程题
省选/NOI-
知识点
题目描述
小 B 有一个很大的数 $S$，长度达到了 $N$ 位；这个数可以看成是一个串，它可能有前导 $0$，例如 `
现在，小 B 提出了 $M$ 个询问，每个询问求 $S$ 的一个子串中有多少子串是 $P$ 的倍数（$0$ 也是 $P$ 的倍数）。例如 $S$ 为 `
00009312345` 。小 B 还有一个素数 $P$。现在，小 B 提出了 $M$ 个询问，每个询问求 $S$ 的一个子串中有多少子串是 $P$ 的倍数（$0$ 也是 $P$ 的倍数）。例如 $S$ 为 `
0077 时，其子串 007 有六个子串：0, 0, 7, 00, 07, 007；显然 0077 的子串 077` 的六个子串都是素数 $7$ 的倍数。输入格式
第一行一个整数：$P$。
第二行一个串：$S$。
第三行一个整数：$M$。
接下来 $M$ 行，每行两个整数 $\text{fr}, \text{to}$，表示对 $S$ 的子串 $S[\text{fr} \ldots \text {to}]$ 的一次询问。
注意：$S$ 的最左端的数字的位置序号为 $1$；例如 $S$ 为 $213567$，则 $S[1]$ 为 $2$，$S[1 \ldots 3]$为 $213$。
第二行一个串：$S$。
第三行一个整数：$M$。
接下来 $M$ 行，每行两个整数 $\text{fr}, \text{to}$，表示对 $S$ 的子串 $S[\text{fr} \ldots \text {to}]$ 的一次询问。
注意：$S$ 的最左端的数字的位置序号为 $1$；例如 $S$ 为 $213567$，则 $S[1]$ 为 $2$，$S[1 \ldots 3]$为 $213$。
输出格式
输出 $M$ 行，每行一个整数，第 $i$ 行是第 $i$ 个询问的答案。
输入输出样例
输入 #1
11 121121 3 1 6 1 5 1 4
输出 #1
5 3 2
说明/提示
对于所有的数据，$N,M \leq 100000$，$P$ 为素数。