AtCoder Beginner Contest 158
翻译中…
Problem Statement
翻译中…
Takahashi has a string $S$ of length $N$ consisting of digits from 0 through 9.
翻译中…
He loves the prime number $P$. He wants to know how many non-empty (contiguous) substrings of $S$ - there are $N \times (N + 1) / 2$ of them - are divisible by $P$ when regarded as integers written in base ten.
翻译中…
Here substrings starting with a 0 also count, and substrings originated from different positions in $S$ are distinguished, even if they are equal as strings or integers.
翻译中…
Compute this count to help Takahashi.
翻译中…
Constraints
翻译中…
$1 \leq N \leq 2 \times 10^5$$S$consists of digits.$|S| = N$$2 \leq P \leq 10000$$P$is a prime number.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N P
S翻译中…
Output
翻译中…
Print the number of non-empty (contiguous) substrings of $S$ that are divisible by $P$ when regarded as an integer written in base ten.
翻译中…
样例
Input #1
4 3
3543
Output #1
6
Here $S$ = `3543`. There are ten non-empty (contiguous) substrings of $S$:
- `3`: divisible by $3$.
- `35`: not divisible by $3$.
- `354`: divisible by $3$.
- `3543`: divisible by $3$.
- `5`: not divisible by $3$.
- `54`: divisible by $3$.
- `543`: divisible by $3$.
- `4`: not divisible by $3$.
- `43`: not divisible by $3$.
- `3`: divisible by $3$.
Six of these are divisible by $3$, so print $6$.
Input #2
4 2
2020
Output #2
10
Here $S$ = `2020`. There are ten non-empty (contiguous) substrings of $S$, all of which are divisible by $2$, so print $10$.
Note that substrings beginning with a `0` also count.
Input #3
20 11
33883322005544116655
Output #3
68
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。