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
121121
3
1 6
1 5
1 4
Sample Output
5
3
2
//第一个询问问的是整个串，满足条件的子串分别有：121121,2112,11,121,121。
3
2
//第一个询问问的是整个串，满足条件的子串分别有：121121,2112,11,121,121。
HINT
2016.4.19新加数据一组
题解：
把后缀模p的数搞出来离散化一下就可以上莫队了
注意p=2或p=5
code：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int64;
char ch;
bool ok;
void read(int &x){
ok=;
for (ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
void read(int64 &x){
ok=;
for (ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
const int maxn=;
char s[maxn];
int n,q,sn,x,y,bel[maxn],tot,cnt[maxn];
int64 mod,a[maxn],ans[maxn],res,pw[maxn],list[maxn];
struct Querys{
int l,r,id;
void init(int i){read(l),read(r),l=n-l+,r=n-r+,swap(l,r),l--,/*cout<<"FFFF "<<l<<' '<<r<<endl,*/id=i;}
}querys[maxn];
bool cmp(const Querys &a,const Querys &b){return bel[a.l]<bel[b.l]||(bel[a.l]==bel[b.l]&&bel[a.r]<bel[b.r]);}
void modify(int col,int op){
if (op==) /*cout<<res<<' '<<col<<' '<<cnt[col]<<endl,*/res+=cnt[col],cnt[col]++;
else cnt[col]--,res-=cnt[col];
}
void work(){
int l=,r=; cnt[a[]]=,res=;
for (int i=;i<=q;i++){
for (;l<querys[i].l;l++) modify(a[l],-);
for (;l>querys[i].l;l--) modify(a[l-],);
for (;r<querys[i].r;r++) modify(a[r+],);
// cout<<"res="<<res<<endl;
for (;r>querys[i].r;r--) modify(a[r],-);
ans[querys[i].id]=res;
}
}
int cnt2[maxn],cnt5[maxn];
int64 ans2[maxn],ans5[maxn];
int main(){
read(mod);
if (mod==){
scanf("%s",s+),n=strlen(s+);
for (int i=;i<=n;i++){
cnt2[i]=cnt2[i-],ans2[i]=ans2[i-];
if ((s[i]-'')%==) cnt2[i]++,ans2[i]+=i;
}
for (read(q);q;q--){
read(x),read(y);
printf("%lld\n",ans2[y]-1LL*(cnt2[y]-cnt2[x-])*(x-)-ans2[x-]);
}
}
else if (mod==){
scanf("%s",s+),n=strlen(s+);
for (int i=;i<=n;i++){
cnt5[i]=cnt5[i-],ans5[i]=ans5[i-];
if ((s[i]-'')%==) cnt5[i]++,ans5[i]+=i;
}
for (read(q);q;q--){
read(x),read(y);
printf("%lld\n",ans5[y]-1LL*(cnt5[y]-cnt5[x-])*(x-)-ans5[x-]);
}
}
else{
scanf("%s",s+),n=strlen(s+),sn=sqrt(n);
for (int i=,j=n;i<j;i++,j--) swap(s[i],s[j]);
for (int i=;i<=n;i++) bel[i]=i/sn;
// for (int i=0;i<=n;i++) cout<<i<<' ';cout<<endl;
// for (int i=0;i<=n;i++) cout<<bel[i]<<' ';cout<<endl;
pw[]=;
for (int i=;i<=n;i++) pw[i]=1LL*pw[i-]*%mod;
for (int i=;i<=n;i++) a[i]=(a[i-]+1LL*(s[i]-'')*pw[i-]%mod)%mod;
for (int i=;i<=n;i++) list[++tot]=a[i];
sort(list+,list+tot+),tot=unique(list+,list+tot+)-list-;
// for (int i=0;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
for (int i=;i<=n;i++) a[i]=lower_bound(list+,list+tot+,a[i])-list;
// for (int i=0;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
read(q);
// cout<<q<<endl;
for (int i=;i<=q;i++) querys[i].init(i);
// for (int i=1;i<=q;i++) cout<<querys[i].l<<' '<<querys[i].r<<' '<<querys[i].id<<endl;
sort(querys+,querys+q+,cmp);
work();
for (int i=;i<=q;i++) printf("%lld\n",ans[i]);
}
return ;
}
/*
11
121121
3
1 6
1 5
1 4
*/