题目概述

有一个字符串，现在问这个字符串的一个子串中有多少子串是给出的素数 $p$ 的倍数（ $0$ 也算）。

解题报告

$10^5$ ？莫队？先把满足条件的子串的式子列出来：$sum_R-sum_{L-1}\times10^{R-L+1}\equiv 0\ (mod\ p)$ 。

那么也就是 $sum_{R}\times 10^{-R}\equiv sum_{L-1}\times10^{-(L-1)}\ (mod\ p)$ ，这个式子就十分舒服，离散一下就可以 $O(1)$ 统计了。

然而……注意 $p=2\lor p=5$ 的时候不存在 $10$ 的逆元，需要特判……考虑原来那个式子，由于 $R-L+1>0$ 所以 $sum_R\equiv 0\ (mod\ p)$ 就行了。

示例程序

#include<cstdio>
#include<algorithm>
#define X first.first
#define Y first.second
#define ID second
using namespace std;
typedef long long LL;typedef pair<pair<int,int>,int> data;
const int maxn=100000,maxq=100000,S=316;

int n,Q,MOD,sum[maxn+5],pw[maxn+5],tem[maxn+5],a[maxn+5];
int HL[maxn+5],HR[maxn+5],Z;LL now,ans[maxq+5];char s[maxn+5];data q[maxq+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline int Find(int x,int L=1,int R=tem[0]){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        if (x==tem[mid]) return mid; else x<tem[mid]?R=mid-1:L=mid+1;
}
inline bool cmp(const data &a,const data &b) {return a.X/S<b.X/S||a.X/S==b.X/S&&((a.X/S&1)?a.Y<b.Y:a.Y>b.Y);}
inline void AddR(int L,int R){if (MOD==2||MOD==5) {if (!sum[R]) now+=R-L+1,Z++;return;}
    HL[a[R-1]]++;if (L<=R) now+=HL[a[R]];HR[a[R]]++;
}
inline void DelR(int L,int R){if (MOD==2||MOD==5) {if (!sum[R]) now-=R-L+1,Z--;return;}
    if (L<=R) now-=HL[a[R]];HL[a[R-1]]--;HR[a[R]]--;
}
inline void AddL(int L,int R){if (MOD==2||MOD==5) {Z+=!sum[L];now+=Z;return;}
    HR[a[L]]++;if (L<=R) now+=HR[a[L-1]];HL[a[L-1]]++;return;
}
inline void DelL(int L,int R){if (MOD==2||MOD==5) {now-=Z;Z-=!sum[L];return;}
    if (L<=R) now-=HR[a[L-1]];HR[a[L]]--;HL[a[L-1]]--;return;
}
int main(){
    freopen("bignum.in","r",stdin);freopen("bignum.out","w",stdout);
    scanf("%d%s%d",&MOD,s+1,&Q);for (n=1;s[n];n++) AMOD(sum[n]=(LL)sum[n-1]*10%MOD,(s[n]-48)%MOD);
    n--;pw[0]=1;pw[1]=Pow(10,MOD-2);for (int i=2;i<=n;i++) pw[i]=(LL)pw[i-1]*pw[1]%MOD;
    for (int i=0;i<=n;i++) tem[++tem[0]]=(LL)sum[i]*pw[i]%MOD;sort(tem+1,tem+1+tem[0]);
    tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;for (int i=0;i<=n;i++) a[i]=Find((LL)sum[i]*pw[i]%MOD);
    for (int i=1;i<=Q;i++) scanf("%d%d",&q[i].X,&q[i].Y),q[i].ID=i;sort(q+1,q+1+Q,cmp);
    for (int i=1,L=1,R=0;i<=Q;ans[q[i++].ID]=now){
        while (R<q[i].Y) AddR(L,++R);while (R>q[i].Y) DelR(L,R--);
        while (L<q[i].X) DelL(L++,R);while (L>q[i].X) AddL(--L,R);
    }for (int i=1;i<=Q;i++) printf("%lld\n",ans[i]);return 0;
}