第一个因为WA 84分的人，另外，求调

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll p,t,blk,n,num[200005],f[200005],ls,rs,sum,mp[200005],ans[200005],cnt;
string s;
struct node{
	ll l,r,ps;
}q[200005];
bool cmp(node x,node y){
	return x.l/blk!=y.l/blk?x.l<y.l:x.r<y.r;
}
void add(ll p,ll g){
	if(g==1){
		sum-=(mp[p]*(mp[p]-1)/2);
		mp[p]++;
		sum+=(mp[p]*(mp[p]-1)/2);
	}
	else{
		sum-=(mp[p]*(mp[p]-1)/2);
		mp[p]--;
		sum+=(mp[p]*(mp[p]-1)/2);
	}
}
int main(){
	cin>>p>>s>>t;
	n=s.length();
	for(int i=1;i<=t;++i) cin>>q[i].l>>q[i].r,q[i].ps=i,q[i].r++;
	blk=sqrt(n);
	sort(q+1,q+1+t,cmp);
	if(p!=5&&p!=2){
		num[n]=f[n]=s[n-1]-'0';
		for(int i=n-1,c=10;i>=1;i--,c=c*10%p){
			num[i]=f[i]=(((s[i-1]-'0')*c%p)+f[i+1])%p;
		}
		sort(num+1,num+1+n);
		cnt=unique(num+1,num+1+n)-num-1;
		for(int i=1;i<=n;i++) f[i]=lower_bound(num+1,num+1+n,f[i])-num;
		ls=1;
		f[n+1]=1;
		for(int i=1;i<=t;i++){
			while(ls<q[i].l){
				add(f[ls],-1);
				ls++;
			}
			while(ls>q[i].l){
				ls--;
				add(f[ls],1);
			}
			while(rs>q[i].r){
				add(f[rs],-1);
				rs--;
			}
			while(rs<q[i].r){
				rs++;
				add(f[rs],1);
			}
			ans[q[i].ps]=sum;
		}
		for(int i=1;i<=t;i++) cout<<ans[i]<<"\n";
	}
	else{
		ls=rs=1;
		if(p==2){
			if((s[0]-'0')%2==0){
				f[0]=1;
				sum++;
			}
			for(int i=1;i<=t;i++){
				while(ls<q[i].l){
					sum-=f[0];
					if((s[ls-1]-'0')%2==0){
						f[0]--;
					}
					ls++;
				}
				while(ls>q[i].l){
					ls--;
					sum+=f[0];
					if((s[ls-1]-'0')%2==0){
						f[0]++;
						sum++;
					}
				}
				while(rs>q[i].r){
					if((s[rs-1]-'0')%2==0){
						f[0]--;
						sum-=(rs-ls+1);
					}
					rs--;
				}
				while(rs<q[i].r){
					rs++;
					if((s[ls-1]-'0')%2==0){
						f[0]++;
						sum+=(rs-ls+1);
					}
				}
				ans[q[i].ps]=sum;
			}
		}
		if(p==2){
			if((s[0]-'0')%5==0){
				f[0]=1;
				sum++;
			}
			for(int i=1;i<=t;i++){
				while(ls<q[i].l){
					sum-=f[0];
					if((s[ls-1]-'0')%5==0){
						f[0]--;
					}
					ls++;
				}
				while(ls>q[i].l){
					ls--;
					sum+=f[0];
					if((s[ls-1]-'0')%5==0){
						f[0]++;
						sum++;
					}
				}
				while(rs>q[i].r){
					if((s[rs-1]-'0')%5==0){
						f[0]--;
						sum-=(rs-ls+1);
					}
					rs--;
				}
				while(rs<q[i].r){
					rs++;
					if((s[ls-1]-'0')%5==0){
						f[0]++;
						sum+=(rs-ls+1);
					}
				}
				ans[q[i].ps]=sum;
			}
		}
		for(int i=1;i<=t;i++) cout<<ans[i]<<"\n";
	}
}