分数: 500 点
问题陈述
高桥有一根绳子 S 长度 N 由以下数字组成 0 通过 9.
他喜欢素数 P。他想知道有多少个非空(连续)子串 S - 有 其中 N \times (N + 1) / 2 - 可被整除 P 当被视为以十为基数书写的整数时。
这里以 a 开头的子字符串 0 也计数,并且子字符串源自于不同位置 S 是有区别的,即使它们作为字符串或整数相等。
计算这个计数来帮助高桥。
约束
- 1 \leq N \leq 2 \times 10^5
- S 由数字组成。
- |S| = N
- 2 \leq P \leq 10000
- P 是素数。
输入
输入由标准输入按以下格式给出:
N P S
输出
打印非空(连续)子串的数量 S 可以被整除 P 被视为以十为基数的整数。
示例输入 1
4 3 3543
示例输出 1
6
这里 S = 3543。有十个非空(连续)子串 S:
-
3:可除以 3. -
35:不能被整除 3. -
354:可除以 3. -
3543:可除以 3. -
5:不能被整除 3. -
54:可除以 3. -
543:可除以 3. -
4:不能被整除 3. -
43:不能被整除 3. -
3:可除以 3.
其中六个可被整除 3,所以打印 6.
示例输入 2
4 2 2020
示例输出 2
10
这里 S = 2020。有十个非空(连续)子串 S,所有这些都可以被整除 2,所以打印 10.
请注意,以 a 开头的子字符串 0 也算。
示例输入 3
20 11 33883322005544116655
示例输出 3
68