題目大意
給出一個長度為 N N N的數字串和一個素數 p p p， M M M組資料求一段子串内為 p p p倍數的子串個數。
解題分析
先假設 p p p不為2和5，那麼對于一個 p p p的倍數 x x x和一個位數為 L L L的數字 y y y，那麼有
x m o d p = 0 x\ mod\ p=0 x mod p=0
y m o d p = z y\ mod\ p=z y mod p=z
( x ∗ 1 0 L + y ) m o d p = ( x ∗ 1 0 L m o d p + y m o d p ) m o d p (x*10^L+y)\ mod\ p=(x*10^L\ mod\ p+y\ mod\ p)\ mod\ p (x∗10L+y) mod p=(x∗10L mod p+y mod p) mod p
= ( x m o d p ∗ 1 0 L m o d p + z ) m o d p = z =(x\ mod\ p*10^L\ mod\ p+z)\ mod\ p=z =(x mod p∗10L mod p+z) mod p=z
是以如果可以弄一個字尾和，那麼發現如果 s u m [ L ] sum[L] sum[L]和 s u m [ R + 1 ] sum[R+1] sum[R+1]關于 p p p同餘，那麼子串 s [ L … R ] s[L\dots R] s[L…R]是p的倍數，是以題目變為找一段區間内 s u m sum sum相等的對數。然後可以離線，明顯莫隊……
如果 p p p為2或5，那麼可以直接查找，因為隻要一個子串的最後一位是 p p p的倍數，那麼這個數就是 p p p的倍數。是以隻要有一個數，那麼從以這個點為右端的所有的這個點到左端點之間的數都是 p p p的倍數。直接 O ( n ) O(n) O(n)預處理再 O ( 1 ) O(1) O(1)輸出就行。
示例代碼
題目傳送門
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,m,p,S,ha[100005],hsh[100005];
LL sum[100005],b[100005],k,ans[100005];
char s[100005];
struct data{
int L,R,id,num;
data (int L=0,int R=0,int id=0):L(L),R(R),id(id){num=S?(L-1)/S:0;}
bool operator < (const data b)const{return num<b.num||(num==b.num&&R<b.R);}
}a[100005];
inline void readi(int &x){
x=0; char ch=getchar();
while ('0'>ch||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
}
void _init(){
freopen("bignum.in","r",stdin);
freopen("bignum.out","w",stdout);
readi(p); scanf("%s",s+1); n=strlen(s+1); readi(m); S=sqrt(n);
for (int i=1,x,y;i<=m;i++){readi(x); readi(y); a[i]=data(x,++y,i);}
}
void _worka(){
for (int i=1;i<=n;i++)
{int pd=((s[i]-'0')%p==0); hsh[i]=hsh[i-1]+pd; sum[i]=sum[i-1]+pd*i;}
for (int i=1;i<=m;i++)
ans[i]=sum[a[i].R-1]-sum[a[i].L-1]-(a[i].L-1)*(hsh[a[i].R-1]-hsh[a[i].L-1]);
}
void _workb(){
sort(a+1,a+m+1); sum[n+1]=k=0; memset(ha,0,sizeof(ha));
LL f=1; for (int i=n;i;i--){b[i]=sum[i]=(sum[i+1]+f*(s[i]-'0')%p)%p; f=f*10%p;}
b[n+1]=0; sort(b+1,b+n+2); b[0]=unique(b+1,b+n+2)-b-1;
for(int i=1;i<=n+1;i++) sum[i]=lower_bound(b+1,b+1+b[0],sum[i])-b;
int L=1,R=0;
for (int i=1;i<=m;i++){
while (R<a[i].R) k+=ha[sum[++R]]++;
while (L>a[i].L) k+=ha[sum[--L]]++;
while (L<a[i].L) k-=--ha[sum[L++]];
while (R>a[i].R) k-=--ha[sum[R--]];
ans[a[i].id]=k;
}
}
void _solve(){
if (p==2||p==5) _worka(); else _workb();
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
int main()
{
_init();
_solve();
return 0;
}