Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 2209 Solved: 839
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新加数据一组
/**************************************************************
Problem: 4542
User: ictsing
Language: C++
Result: Accepted
Time:4988 ms
Memory:9652 kb
****************************************************************/
/*
多次询问区间，并不强制在线，可以考虑莫队算法。
首先有性质，如果一个数的后缀[r,n],[l,n]modp相等，
那么[l,r-1]是p的倍数。
我们来证明一下这个：
[r,n]=t'
[l,r-1]=t
那么[l,n]=t*10^(n-r+1)+t'=w
假设t'%p=x,w%p=x
那么显然t%p=x
?!
如果p是10的因数，即p=2或5，
那么这个结论就是错的，因为无论怎么取都是相等的。
那么p=2或5的时候特判一下就好了。
怎么特判呢？
我们维护一个前缀和，如果这个前缀是2或5的倍数那么前缀加，
再开一个计数的，表示这个前缀可以和几个组合。
然后再考虑其他情况怎么做。
我们预处理出num[i]，表示[i,n]modp的余数。
然后开一个cnt[]来记录每个数在当前区间出现次数。
但是注意到p可能非常的大，我们想办法离散化一下。
我们把得到的所有的num[i]sort一遍。
每个值映射到他出现的第一个位置上，
那么这个cnt[]最大也就只是n了。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const ll mt = 100000+5;
inline ll readll()
{
ll num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
ll sz;
char s[mt];
struct ques
{
ll l,r,id;
}q[mt];
ll ans_[mt];
ll num[mt],qaq[mt];
bool cmp(ques a,ques b)
{
if((a.l-1)/sz==(b.l-1)/sz) return a.r<b.r;
return (a.l-1)/sz<(b.l-1)/sz;
}
ll cnt[mt];
map<ll,ll>map_;
int main()
{
ll p=readll();
scanf("%s",s+1);
ll len=strlen(s+1);
ll m=readll();
if(p!=2&&p!=5)
{
sz=sqrt(len);
ll number=0;
ll bas=1;
for(ll i=len;i>=1;i--)
{
number=(number+(s[i]-'0')*bas)%p;
bas=bas*10%p;
qaq[i]=num[i]=number;
//cout<<qaq[i]<<endl;
}
sort(qaq+1,qaq+len+1);
for(ll i=1;i<=len+1;i++)
if(!map_[qaq[i]]) map_[qaq[i]]=i;
for(ll i=1;i<=len+1;i++)
num[i]=map_[num[i]];
for(ll i=1;i<=m;i++)
{
q[i].l=readll(),q[i].r=readll(),q[i].id=i;
q[i].r++;
}
sort(q+1,q+m+1,cmp);
ll L=1,R=0,ans=0;
for(ll i=1;i<=m;i++)
{
while(R<q[i].r) R++,ans+=cnt[num[R]],cnt[num[R]]++;
while(L>q[i].l) L--,ans+=cnt[num[L]],cnt[num[L]]++;
while(L<q[i].l) cnt[num[L]]--,ans-=cnt[num[L]],L++;
while(R>q[i].r) cnt[num[R]]--,ans-=cnt[num[R]],R--;
ans_[q[i].id]=ans;
}
for(ll i=1;i<=m;i++)
printf("%lld\n",ans_[i]);
}
else
{
ll number=0;
for(ll i=1;i<=len;i++)
{
number=number+s[i]-'0';
if(!(number%p))
num[i]=num[i-1]+1,cnt[i]=cnt[i-1]+i;
else num[i]=num[i-1],cnt[i]=cnt[i-1];
number=number*10;
}
for(ll i=1;i<=m;i++)
{
ll l=readll(),r=readll();
ll ans=cnt[r]-cnt[l-1]-(num[r]-num[l-1])*(l-1);
printf("%lld\n",ans);
}
}
return 0;
}
评论