#P3245. [HNOI2016] 大数

[HNOI2016] 大数

题目描述

小 B 有一个很大的数 SS,长度达到了 nn 位;这个数可以看成是一个数字串,它可能有前导 00,例如 00009312345。小 B 还有一个素数 pp。现在,小 B 提出了 mm 个询问,每个询问求 SS 的一个子串中有多少子串是 pp 的倍数(00 也是 pp 的倍数)。例如 SS0077 时,其子串 00766 个子串:0,0,7,00,07,007;显然 0077 的子串 00766 个子串都是素数 77 的倍数。

输入格式

第一行一个整数:pp

第二行一个数字串:SS

第三行一个整数:mm。接下来 mm 行,每行两个整数 fr,tofr,to,表示对 SS 的子串 S[frto]S[fr\dots to] 的一次询问。注意:SS 的最左端的数字的位置序号为 11;例如 SS213567,则 S[13]S[1\dots 3]213

输出格式

输出 mm 行,每行一个整数,第 ii 行是第 ii 个询问的答案。

11
121121
3
1 6
1 5
1 4
5
3
2
//第一个询问问的是整个串,满足条件的子串分别有:121121,2112,11,121,121。

提示

样例 1 解释

第一个询问问的是整个串,满足条件的子串分别有:121121,2112,11,121,121

数据范围

对于 100%100\% 的数据,1n,m2×1051\le n,m\le 2\times 10^52p1092\le p\le 10^9SS 中只有数字字符,pp 为素数。