← 返回题目
题库练习 亲朋数
← 上一题 下一题 →

A71543 | 亲朋数

来源编程题
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一串长度为 L、由数字 0 - 9 组成的数字串 S 。容易知道，它的连续子串共有 \frac{L(L+1)}{2} 个。如果某个子串对应的数（允许有前导零）是 p 的倍数，则称该子串为数字串 S 对于 p 的亲朋数。

例如，数字串 S 为 “12342”、p为 2，则在 15 个连续子串中，亲朋数有 “12”、“1234”、“12342”、“2”、“234”、“2342”、“34”、“342”、“4”、“42”、“2” 等共 11 个。注意其中 “2” 出现了 2 次，但由于其在 S 中的位置不同，记为不同的亲朋数。

现在，告诉你数字串 S 和正整数 p，你能计算出有多少个亲朋数吗？

输入格式

输入的第一行，包含一个正整数 p。约定 2 ≤ p ≤ 128。

输入的第二行，包含一个长为 L 的数字串S。约定 1 ≤ L ≤ 10^6 。

输出格式

输出一行，包含一个正整数 C，表示亲朋数的个数。

输入输出样例

输入 #1
2
102
输出 #1
5
输入 #2
2
12342
输出 #2
11
C++ 编辑器
输入
输出