Base n

题目描述

给定一个由数字 $0$ 到 $9$ 组成的字符串 $X$，以及一个整数 $M$。 令 $d$ 为 $X$ 中最大的数字。 通过选择一个不小于 $d+1$ 的整数 $n$ 并将 $X$ 视为以基数 $n$ 的数，可以得到多少个不大于 $M$ 的不同整数？

输入格式

输入按下列格式从标准输入给出： $X$ $M$

输出格式

输出答案。

22
10

2

999
1500

3

100000000000000000000000000000000000000000000000000000000000
1000000000000000000

1

提示

$X$ 由数字 $0$ 到 $9$ 组成。 $X$ 的长度在 $1$ 到 $60$（含）之间。 $X$ 不以 $0$ 开头。 $1 \leq M \leq 10^{18}$$X$ 中最大的数字是 $2$。

将 $X$ 视为基数为 $3$ 的数时，我们得到 $8$。 将 $X$ 视为基数为 $4$ 的数时，我们得到 $10$。

这两个值是我们可以得到且不大于 $10$ 的唯一值。
$X$ 中最大的数字是 $9$。

将 $X$ 视为基数为 $10$ 的数时，我们得到 $999$。 将 $X$ 视为基数为 $11$ 的数时，我们得到 $1197$。 将 $X$ 视为基数为 $12$ 的数时，我们得到 $1413$。

这三个值是我们可以得到且不大于 $1500$ 的唯一值。
将 $X$ 视为基数为 $2$ 的数时，我们得到 $576460752303423488$，这是我们可以得到且不大于 $1000000000000000000$ 的唯一值。

标签: AtCoder|abc192D

来源

AtCoder|abc192D