Description
小 B 有一个很大的数 S，长度达到了 N 位；这个数可以看成是一个串，它可能有前导 0，例如00009312345
。小B还有一个素数P。现在，小 B 提出了 M 个询问，每个询问求 S 的一个子串中有多少子串是 P 的倍数（0 也 是P 的倍数）。例如 S为0077时，其子串 007有6个子串：0,0,7,00,07,007；显然0077的子串007有6个子串都是素 数7的倍数。Input
第一行一个整数：P。第二行一个串：S。第三行一个整数：M。接下来M行，每行两个整数 fr,to，表示对S 的
子串S[fr…to]的一次询问。注意：S的最左端的数字的位置序号为 1；例如S为213567，则S[1]为 2，S[1…3]为 2 13。N,M<=100000，P为素数Output
输出M行，每行一个整数，第 i行是第 i个询问的答案。
Sample Input
11 121121 3 1 6 1 5 1 4
Sample Output
5 3 2 //第一个询问问的是整个串，满足条件的子串分别有：121121,2112,11,121,121。
HINT
2016.4.19新加数据一组
Solution
设$num_i$ 表示 $[i...n]$的数
则$[l...r]$的数为$p$的倍数时有$\frac{num_{l-1}-num_{r}}{10^{r-l+1}}\space mod\space p = 0$
因为$p$为质数，所以$10^{r-l+1}$与$p$互质,即$num_{l-1}\equiv num_{r}(mod\space p)$
离散化num，用莫队统计答案即可
#include#define ll long long#define inf 0x3f3f3f3f#define il inlinenamespace io { #define in(a) a=read() #define out(a) write(a) #define outn(a) out(a),putchar('\n') #define I_int int inline I_int read() { I_int x = 0 , f = 1 ; char c = getchar() ; while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } return x * f ; } char F[ 200 ] ; inline void write( I_int x ) { if( x == 0 ) { putchar( '0' ) ; return ; } I_int tmp = x > 0 ? x : -x ; if( x < 0 ) putchar( '-' ) ; int cnt = 0 ; while( tmp > 0 ) { F[ cnt ++ ] = tmp % 10 + '0' ; tmp /= 10 ; } while( cnt > 0 ) putchar( F[ -- cnt ] ) ; } #undef I_int}using namespace io ;using namespace std ;#define N 100010int cnt[N] , rnk[N] ; ll Ans[N] ;ll sum1[N] , sum2[N] , P , ans ;char s[N] ; int block ;struct node { int l , r , id ;} a[N] ;struct date { ll val ; int id ;} data[N] ;bool cmp(node a , node b) { return a.l / block == b.l / block ? a.r < b.r : a.l < b.l ; }bool cmp2(date a , date b) { return a.val < b.val ; }/*num_i 表示 [i...n]的数 \\则[l...r]的数为p的倍数时有\frac{num_{l-1}-num_{r}}{10^{r-l+1}}\space mod\space p = 0 \\因为p为质数，所以10^{r-l+1}与p互质,即num_{l-1}\equiv num_{r}(mod\space p) \\*/void add(int x) { ans += cnt[rnk[x]] ++ ; }void del(int x) { ans -= -- cnt[rnk[x]] ; }int main() { int p = read() ; scanf("%s" , s + 1) ; int n = strlen(s + 1) , m = read() ; if(p == 2 || p == 5) { for(int i = 1 ; i <= n ; i ++) { sum1[i] = sum1[i - 1] ; sum2[i] = sum2[i - 1] ; if((s[i] - '0') % p == 0) sum1[i] ++ , sum2[i] += i; } for(int i = 1 ; i <= m ; i ++) { int l = read() , r = read() ; printf("%lld\n" , sum2[r] - sum2[l - 1] - (sum1[r] - sum1[l - 1])*(l - 1)) ; } return 0 ; } P = 1 ; for(int i = 1 ; i <= m ; i ++) a[i] = (node) {read() , read() + 1, i} ; block = sqrt(n) ; sort(a + 1 , a + m + 1 , cmp) ; for(int i = n ; i ; i --) P = P * 10 % p , data[i] = (date) {((s[i] - '0') * P % p + data[i+1].val) % p, i} ; sort(data + 1 , data + n + 1 , cmp2) ; for(int i = 1 ; i <= n + 1 ; i ++) { if(data[i].val == data[i-1].val) rnk[data[i].id] = rnk[data[i-1].id] ; else rnk[data[i].id] = i ; } int l = 1 , r = 0 ; for(int i = 1 ; i <= m ; i ++) { int ql = a[i].l , qr = a[i].r ; while(l < ql) del(l++) ; while(l > ql) add(--l) ; while(r > qr) del(r--) ; while(r < qr) add(++r) ; Ans[ a[i].id ] = ans ; } for(int i = 1 ; i <= m ; i ++) printf("%lld\n",Ans[i]) ; return 0 ;}