#ABC158E. Divisible Substring
Divisible Substring
题目描述
Takahashi has a string of length consisting of digits from 0
through 9
.
He loves the prime number . He wants to know how many non-empty (contiguous) substrings of - there are of them - are divisible by when regarded as integers written in base ten.
Here substrings starting with a 0
also count, and substrings originated from different positions in are distinguished, even if they are equal as strings or integers.
Compute this count to help Takahashi.
高桥有一个长度为 的字符串 ,由从
0
到9
的数字组成。他喜欢质数 。他想知道 的非空(连续)子串 有多少个。- 有 个--如果看作以十为底数的整数,则可以被 整除。
在这里,以 "0 "开头的子串也算数,而且从 的不同位置开始的子串也要加以区分,即使它们作为字符串或整数是相等的。
计算这个计数来帮助高桥。
输入格式
输入内容按以下格式标准输入:
输出格式
打印 的非空(连续)子串中,能被 整除(以十为基数)的个数。
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
样例 #3
样例输入 #3
样例输出 #3
说明
数据规模与约定
- 由数字组成。
- 是质数。
样例 解释
此处 = 3543
。 有十个非空(连续)子串:
-
3`:可被 整除。
-
35`:不能被 整除。
-
354`:能被 整除。
-
3543`:可以被 整除。
-
5`:不能被 整除。
-
54`:能被 整除。
-
543`:能被 整除。
-
4`:不能被 整除。
-
43`:不能被 整除。
-
3`:不能被 整除。
其中 6 个能被 整除,因此打印 。
样例 解释
这里 = 2020
。 有 10 个非空(连续)子串,它们都能被 整除,因此打印 。
请注意,以 "0 "开头的子串也算数。