Description

　　小 B 有一個(gè)很大的數(shù) S，長(zhǎng)度達(dá)到了 N 位；這個(gè)數(shù)可以看成是一個(gè)串，它可能有前導(dǎo) 0，例如00009312345。小B還有一個(gè)素?cái)?shù)P。現(xiàn)在，小 B 提出了 M 個(gè)詢問，每個(gè)詢問求 S 的一個(gè)子串中有多少子串是 P 的倍數(shù)（0 也是P 的倍數(shù)）。例如 S為0077時(shí)，其子串 007有6個(gè)子串：0,0,7,00,07,007；顯然0077的子串007有6個(gè)子串都是素?cái)?shù)7的倍數(shù)。

Input

　　第一行一個(gè)整數(shù)：P。第二行一個(gè)串：S。第三行一個(gè)整數(shù)：M。接下來M行，每行兩個(gè)整數(shù) fr,to，表示對(duì)S 的子串S[fr…to]的一次詢問。注意：S的最左端的數(shù)字的位置序號(hào)為 1；例如S為213567，則S[1]為 2，S[1…3]為 213。N,M<=100000，P為素?cái)?shù)

Output

　　輸出M行，每行一個(gè)整數(shù)，第 i行是第 i個(gè)詢問的答案。

Sample Input

Sample Output

HINT

 2016.4.19新加數(shù)據(jù)一組

正解：莫隊(duì)算法。

考慮每次端點(diǎn)移動(dòng)以后能產(chǎn)生的新貢獻(xiàn)。用一個(gè)數(shù)組val[i]表示這個(gè)數(shù)只保留前i位上的數(shù)，其他位都是0的數(shù)模p的余數(shù)。那么如果val[l-1]=val[r]，那么[l,r]區(qū)間上這個(gè)數(shù)模p=0。所以只要求出這個(gè)數(shù)組，并把n+1，同時(shí)n+1位為0，所有詢問的右端點(diǎn)+1，這樣，就能很好處理了。當(dāng)指針移動(dòng)時(shí)，只要查詢與當(dāng)前val相等的個(gè)數(shù)即可。因?yàn)関al很大，所以要離散化。注意p=2或5時(shí)要加特判，因?yàn)橹灰詈笠晃荒?或5為0，那么這個(gè)數(shù)就是2或5的倍數(shù)。所以就很容易了。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define il inline#define RG register#define ull unsigned long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;struct node{ ull l,r,i; }q[100010];ull c[100010],bl[100010],po[100010],val[100010],num[100010],hsh[100010],ans[100010],pp[100010],PRe[100010],n,m,p,tot,block;char s[100010];il ull gll(){    RG ull x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il int cmp(const node &a,const node &b){ return bl[a.l]<bl[b.l] || (bl[a.l]==bl[b.l] && a.r<b.r); }il void solve(){    for (RG ull i=1;i<=n;++i) pre[i]=pre[i-1]+((s[i]-48)%p==0),pp[i]=pp[i-1]+i*((s[i]-48)%p==0);    for (RG ull i=1;i<=m;++i){	RG ull l=gll(),r=gll();	printf("%llu/n",pp[r]-pp[l-1]-(pre[r]-pre[l-1])*(l-1));    }    return;}il void work(){    scanf("%llu%s%llu",&p,s+1,&m); n=strlen(s+1);    if (p==2 || p==5){ solve(); return; } block=sqrt(n);    for (RG ull i=1;i<=m;++i) q[i].l=gll(),q[i].r=gll()+1,q[i].i=i;    for (RG ull i=1;i<=n;++i) bl[i]=(i-1)/block+1; sort(q+1,q+m+1,cmp);    po[n]=1; for (RG ull i=n-1;i;--i) po[i]=po[i+1]*10%p;    for (RG ull i=n;i;--i) num[i]=val[i]=(val[i+1]+(s[i]-48)*po[i])%p; sort(num+1,num+n+2);    hsh[tot=1]=num[1]; for (RG ull i=2;i<=n+1;++i) if (num[i]>num[i-1]) hsh[++tot]=num[i];    for (RG ull i=1;i<=n+1;++i) val[i]=lower_bound(hsh+1,hsh+tot+1,val[i])-hsh; ull L=1,R=0,Ans=0;    for (RG ull i=1;i<=m;++i){	while (L>q[i].l) L--,Ans+=c[val[L]],c[val[L]]++;	while (R<q[i].r) R++,Ans+=c[val[R]],c[val[R]]++;	while (L<q[i].l) c[val[L]]--,Ans-=c[val[L]],L++;	while (R>q[i].r) c[val[R]]--,Ans-=c[val[R]],R--;	ans[q[i].i]=Ans;    }    for (RG ull i=1;i<=m;++i) printf("%llu/n",ans[i]); return;}int main(){    File("number");    work();    return 0;}