题意:
小 $B$ 有一个很大的数 $S$，长度达到了 $N$ 位；这个数可以看成是一个串，它可能有前导 $0$，例如 $00009312345$。小 $B$ 还有一个素数 $P$。
现在，小 $B$ 提出了 $M$ 个询问，每个询问求 $S$ 的一个子串中有多少子串是 $P$ 的倍数（$0$ 也是 $P$ 的倍数）。例如 $S$ 为 $0077$ 时，其子串 $007$ 有六个子串：$0, 0, 7, 00, 07, 007$。显然 $0077$ 的子串 $077$ 的六个子串都是素数 $77$ 的倍数。
$N,M<=10^5$，$P<=10^9$
题解:
如果直接求一个序列的答案，发现并不好求。于是考虑求以 $l$ 为左端点（右端点类似）所造成的贡献，显然，当满足 $frac{s[r]-s[l-1]}{10^{n-r}}=0 (mod p)$，就找到了一个合法的区间（$s[i]$ 表示由前 $i$ 个数和后 $n-i$ 个 $0$ 构成的数字）。这样我们发现，假设我们已知一个区间的答案，可以做到 $O(1)$ 移动一个单位的端点。而我们要求的，实际上就是区间中等于某个数的位置个数。可以将其离散化之后，用莫队+桶维护。
当 $p=5$ 或 $p=2$ 时需要特殊处理，可以发现此时的数字只与个位数有关，随便维护一下就好了。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; int mod,n,m,fk,s[100002],sn[100002],num[100002],t[100002],cf[100002]; long long ans[100002],nans; char ch[100002]; typedef struct{ int l,r,num; }P; bool cmp(P aa,P bb){ return (aa.l/fk<bb.l/fk || aa.l/fk==bb.l/fk && aa.r<bb.r); } P p[100002]; int main() { scanf("%d%s%d",&mod,ch+1,&m);n=strlen(ch+1);fk=sqrt(n); for (int i=1;i<=m;i++) { scanf("%d%d",&p[i].l,&p[i].r);p[i].num=i; } sort(p+1,p+m+1,cmp); if (mod==2) { int l=p[1].l,r=p[1].l; if ((ch[l]-'0')%mod==0)nans=1;else nans=0; num[ch[l]-'0']++; for (int i=1;i<=m;i++) { while(l>p[i].l) { l--; num[ch[l]-'0']++;nans+=num[0]+num[2]+num[4]+num[6]+num[8]; } while(r<p[i].r) { r++; num[ch[r]-'0']++;if ((ch[r]-'0')%2==0)nans+=r-l+1; } while(l<p[i].l) { nans-=num[0]+num[2]+num[4]+num[6]+num[8];num[ch[l]-'0']--; l++; } while(r>p[i].r) { if ((ch[r]-'0')%2==0)nans-=r-l+1;num[ch[r]-'0']--; r--; } ans[p[i].num]=nans; } for (int i=1;i<=m;i++)printf("%lld ",ans[i]); return 0; } else if (mod==5) { int l=p[1].l,r=p[1].l; if ((ch[l]-'0')%mod==0)nans=1;else nans=0; num[ch[l]-'0']++; for (int i=1;i<=m;i++) { while(l>p[i].l) { l--; num[ch[l]-'0']++;nans+=num[0]+num[5]; } while(r<p[i].r) { r++; num[ch[r]-'0']++;if ((ch[r]-'0')%5==0)nans+=r-l+1; } while(l<p[i].l) { nans-=num[0]+num[5];num[ch[l]-'0']--; l++; } while(r>p[i].r) { if ((ch[r]-'0')%5==0)nans-=r-l+1;num[ch[r]-'0']--; r--; } ans[p[i].num]=nans; } for (int i=1;i<=m;i++)printf("%lld ",ans[i]); return 0; } cf[0]=1; for (int i=1;i<=n;i++)cf[i]=(long long)cf[i-1]*10%mod; for (int i=1;i<=n;i++)t[i]=s[i]=(s[i-1]+(long long)(ch[i]-'0')*cf[n-i])%mod; t[n+1]=0;sort(t+1,t+n+2); for (int i=0;i<=n;i++)sn[i]=lower_bound(t+1,t+n+2,s[i])-t; int l=p[1].l,r=p[1].l; if ((ch[l]-'0')%mod==0)nans=1;else nans=0; num[sn[l]]++; for (int i=1;i<=m;i++) { while(l>p[i].l) { l--; num[sn[l]]++;nans+=num[sn[l-1]]; } while(r<p[i].r) { r++; num[sn[r]]++;nans+=num[sn[r]]-1+(sn[l-1]==sn[r]); } while(l<p[i].l) { nans-=num[sn[l-1]];num[sn[l]]--; l++; } while(r>p[i].r) { nans-=num[sn[r]]-1+(sn[l-1]==sn[r]);num[sn[r]]--; r--; } ans[p[i].num]=nans; } for (int i=1;i<=m;i++)printf("%lld ",ans[i]); return 0; }