CF1400F x-prime Substrings

给定一个整数 $x$ 和一个只包含数字 $1$ 到 $9$ 的字符串 $s$。 字符串的子串是该字符串的一个连续子序列。 设 $f(l, r)$ 表示子串 $s[l..r]$ 的数字之和。 我们称子串 $s[l_1..r_1]$ 为 $x$-prime，当且仅当： - $f(l_1, r_1) = x$； - 不存在 $l_2, r_2$ 满足： - $l_1 \le l_2 \le r_2 \le r_1$； - $f(l_2, r_2) \neq x$； - $x$ 能被 $f(l_2, r_2)$ 整除。 你可以从字符串中删除一些字符。每删除一个字符，字符串会被分成两部分并直接拼接，顺序不变。 请问，最少需要删除多少个字符，才能使字符串中不存在 $x$-prime 子串？如果原字符串中本就不存在 $x$-prime 子串，则输出 $0$。

第一行输入字符串 $s$（$1 \le |s| \le 1000$），$s$ 只包含数字 $1$ 到 $9$。 第二行输入一个整数 $x$（$1 \le x \le 20$）。

输出一个整数，表示最少需要删除多少个字符，才能使字符串中不存在 $x$-prime 子串。如果原字符串中不存在 $x$-prime 子串，则输出 $0$。

在第一个样例中，有两个 $8$-prime 子串 "8" 和 "53"。你可以删除这些字符来消除它们："116285317"。删除后得到的字符串 "1162317" 不再包含 $8$-prime 子串。删除这些字符也是一个合法答案："116285317"。 在第二个样例中，你只需要删除两个 $1$。 在第三个样例中，没有 $13$-prime 子串。实际上，没有任何子串的数字和等于 $13$。 在第四个样例中，字符串中不能同时包含 "34" 和 "43"。因此，你必须删除所有的 $3$ 或所有的 $4$。两者各有 $5$ 个，删除哪一个都可以。 由 ChatGPT 4.1 翻译