题意

给一个 N 位的可能有前导 0 的数 S 及一个素数 P 。 M 个询问，每个询问求 S 的一个字串中有多少子串是 P 的倍数( 0 也是 P 的倍数)。
N,M≤105 ， P<1010

解法

???? 对于询问 [l,r] ，我们要求的相当于

???? 因为题目保证了 P 为质数，所以当 P≠2 且 P≠5 时， 10k 存在逆元，且 10jmodP≠0 。设 a[i]=s[i]?(10i)?1modP，sum[i] 为 a[i] 模 P 下前缀和。
原式 =∑i=lr∑j=ir[(∑k=ija[k])modP=0]
?????=∑i=lr∑j=ir[(sum[j]?sum[i?1])modP=0]
?????=∑i=lr∑j=ir[(sum[j]=sum[i?1])]
对于多组询问，这就是一个经典的莫队了。将 sum 数组离散化，开一个桶记录一下 sum[i] 这个数值已经出现了多少次，移动左右端点时更新一下就行了。
???? 而当 P=2 或 P=5 时，答案比较好推，这里就不赘述了。
???? 注意可能爆 long?long