{"problem":{"name":"[GESP样题 六级] 亲朋数","description":{"content":" 给定一串长度为 $L$、由数字 $0\\sim 9$ 组成的数字串 $S$。容易知道，它的连续子串共有 $\\frac{L(L + 1)}2$ 个。如果某个子串对应的数（允许有前导零）是 $p$ 的倍数，则称该子串为数字串 $S$ 对于 $p$ 的亲朋数。 例如，数字串 $S$ 为“ $12342$ ”、$p$ 为 $2$，则在 $15$ 个连续子串中，亲朋数有“ $12$ ”、“ $1234$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10262"},"statements":[{"statement_type":"Markdown","content":"给定一串长度为 $L$、由数字 $0\\sim 9$ 组成的数字串 $S$。容易知道，它的连续子串共有 $\\frac{L(L + 1)}2$ 个。如果某个子串对应的数（允许有前导零）是 $p$ 的倍数，则称该子串为数字串 $S$ 对于 $p$ 的亲朋数。\n\n例如，数字串 $S$ 为“ $12342$ ”、$p$ 为 $2$，则在 $15$ 个连续子串中，亲朋数有“ $12$ ”、“ $1234$ ”、“ $12342$ ”、“ $2$ ”、“ $234$ ”、“ $2342$ ”、“ $34$ ”、“ $342$ ”、“ $4$ ”、“ $42$ ”、“ $2$ ”共 $11$ 个。注意其中“ $2$ ”出现了 $2$ 次，但由于其在 $S$ 中的位置不同，记为不同的亲朋数。\n\n现在，告诉你数字串 $S$ 和正整数 $p$ ，你能计算出有多少个亲朋数吗？\n\n## Input\n\n输入的第一行，包含一个正整数 $p$。约定 $2 \\leq p \\leq 128$。  \n输入的第二行，包含一个长为 $L$ 的数字串 $S$。约定 $1 \\leq L \\leq 10^6$。\n\n## Output\n\n输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1106>\n\n## Note\n\n## 样例 1 解释\n\n$5$ 个亲朋数，分别 $10$、$102$、$0$、$02$、$2$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10262","tags":["动态规划 DP","GESP"],"sample_group":[["2\n102","5\n"],["2\n12342","11"]],"created_at":"2026-03-03 11:09:25"}}