AT_abc158_e [ABC158E] Divisible Substring

题目描述

高桥君有一个由数字 $0$ 到 $9$ 组成、长度为 $N$ 的字符串 $S$。

高桥君喜欢素数 $P$，他想知道，在 $S$ 的所有 $N \times (N + 1) / 2$ 个非空连续子串中，有多少个子串在视为十进制整数时能够被 $P$ 整除。

注意，子串可以以 $0$ 开头；即使作为字符串或整数相等，只要在 $S$ 中的位置不同，也要分别计数。

请你帮高桥君计算这个数量。

输入格式

输入以以下格式从标准输入读入。

$N$ $P$ $S$

输出格式

输出 $S$ 的所有非空连续子串中，能被 $P$ 整除的子串的个数。

输入输出样例 #1

输入 #1

4 3
3543

输出 #1

6

输入输出样例 #2

输入 #2

4 2
2020

输出 #2

10

输入输出样例 #3

输入 #3

20 11
33883322005544116655

输出 #3

68

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $S$ 只包含数字
• $|S| = N$
• $2 \leq P \leq 10000$
• $P$ 是素数

样例解释 1

$S = 3543$。$S$ 的所有非空连续子串共有 $10$ 个，如下所示：

• 3 可以被 $3$ 整除。
• 35 不能被 $3$ 整除。
• 354 可以被 $3$ 整除。
• 3543 可以被 $3$ 整除。
• 5 不能被 $3$ 整除。
• 54 可以被 $3$ 整除。
• 543 可以被 $3$ 整除。
• 4 不能被 $3$ 整除。
• 43 不能被 $3$ 整除。
• 3 可以被 $3$ 整除。

其中能被 $3$ 整除的有 $6$ 个，所以输出 $6$。

样例解释 2

$S = 2020$。$S$ 的所有非空连续子串共有 $10$ 个，并且全部都能被 $2$ 整除，所以输出 $10$。注意允许以 $0$ 开头的子串。

由 ChatGPT 4.1 翻译