abc158 E

abc158 E Divisible Substring

比赛的时候居然没做出来。。。几个星期没做题，思维能力真是呈几何级数下降。

题意

求一个 ’0‘ 到 ‘9’ 组成的数字串有多少子串(连续)能被质数 p 整除。

数据范围

• (1le Nle 2×10^5)
• (S) consists of digits.
• $|S|=N $
• (2le Ple 10000)
• (P) is a prime number.

解法

• 对于2和5，能否整除取决于子串的最后一位，故可以一遍遍历得出答案。

• 对于其他质数。如果 (W) 能被 (P) 整除，则 (W) 除去结尾的任意个 0 (如果有的话)同样可以被 (P) 整除，因为 10 不能提供 P 的因子。

• 因此我们可以用一个数组num来求答案，令(num[i]=(s[i]-'0')*10^{n-i}\%p) 。我们可以发现某个子串能被 P 整除对应于 num 数组中的对应区间和能被 (P) 整除。

• 求有多少个区间的问题利用数组的前缀和加map就可以解决。