AT_abc192_d [ABC192D] Base n

题目描述

给定一个只包含数字 $0$ 到 $9$ 的字符串 $X$，以及一个整数 $M$。

设 $X$ 中出现的最大数字为 $d$。

请问，有多少个大于等于 $d+1$ 的整数 $n$，使得将 $X$ 视为 $n$ 进制下的数时，其值不超过 $M$？

输入格式

输入以如下格式从标准输入读入。

$X$ $M$

输出格式

输出答案。

样例 1

输入

22
10

输出

2

样例 2

输入

999
1500

输出

3

样例 3

输入

100000000000000000000000000000000000000000000000000000000000
1000000000000000000

输出

1

说明/提示

限制条件

• $X$ 仅由数字 $0$ 到 $9$ 组成。
• $X$ 的长度为 $1$ 到 $60$。
• $X$ 的首位不是 $0$。
• $1 \leq M \leq 10^{18}$。

样例解释 1

$X$ 中出现的最大数字为 $2$。

• 将 $X$ 视为 $3$ 进制时的值为 $8$。
• 将 $X$ 视为 $4$ 进制时的值为 $10$。 在这些值中，不超过 $10$ 的有 $2$ 个。

样例解释 2

$X$ 中出现的最大数字为 $9$。

• 将 $X$ 视为 $10$ 进制时的值为 $999$。
• 将 $X$ 视为 $11$ 进制时的值为 $1197$。
• 将 $X$ 视为 $12$ 进制时的值为 $1413$。 在这些值中，不超过 $1500$ 的有 $3$ 个。

样例解释 3

将 $X$ 视为 $2$ 进制时的值为 $576460752303423488$，这是唯一一个不超过 $1000000000000000000$ 的值。

由 ChatGPT 4.1 翻译