← 返回题目列表

AtCoder · abc158_e

E. 可整除子串

中文机器翻译题面 查看原题

分数: 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