P3245 题解 最后更新于 2025-05-02 00:00:40

## 题意 给定一个只包含数字的字符串 $S$ 和模数 $p$ 。$m$ 次询问，每次查询区间 $[l,r]$ 内有多少个连续子串在十进制下是 $p$ 的倍数，忽略前导零（但是零也是 $p$ 的倍数）。 $n,m\le 2\times 10^5,\ p\le 10^9$ ## 思路 分两种情况讨论。 - $p\neq 2 \ ,\ p \neq 5$ 此时我们可以记录 $S$ 的每一个后缀对 $p$ 取模的结果。则两个后缀 $suf_i,suf_j$ 之差可以表示为 $10^{i-j}\times S[i,j-1]$ 。当 $suf_i = suf_j$ 时 $S[i,j-1]$ 即为 $p$ 的倍数。那么求区间 $[l,r]$ 内 $p$ 的倍数的子串个数就是求有多少对 $(i,j)$ 满足 $suf_i= suf_j$ 且 $l\le i < j\le r$ 。莫队求解即可。时间复杂度 $O(n\sqrt{n})$ 。 - $p=2$ 或 $p=5$ 上面的方法行不通，因为 $10^{i-j}$ 中含有大量的质因子 `2` 和 `5` 。注意到此时 $p$ 很小，所以我们可以预处理前缀和，每次询问统计后直接输出答案。小容斥，推推式子还是能挺快做出来的。时间复杂度 $O(n+m)$ 。