You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定正整数$n$ 和初始数$x$， 你可以对$x$ 执行若干次操作，每次操作定义如下： 从$x$ 当前的十进制表示中选择任意一个数字 $d\in\{2,3,\dots,9\}$，并将$x$更新为 $x \times d$。

目标：你的目标是使$x$ 的十进制表示长度（不含前导零）达到至少$n$ 位。求最少操作次数；如果无法在有限次操作内达到目标，请输出$-1$。

输入格式

一行两个整数 $n,x$。

输出格式

输出最少操作次数，无解输出 $-1$。

输入输出样例

样例1 输入：3 100 输出：0

样例2 输入：2 9 输出：1

数据范围

对于 $60\%$ 的数据满足 $2\le n \leq 19$。

对于 $20\%$ 的数据满足$n =20$。

对于$10\%$ 的数据，$n =10$。

对于 $10\%$ 的数据，$n=30$。

特别说明：题目保证输入的初始值 以及最终答案所在的数值范围均在 int 以内，

提示

由于搜索过程中产生的中间数字可能超过 64 位整数的表示范围，可使用 __int128

类型进行数值存储与计算。

__int128

使用简要说明：

__int128 是 GCC 编译器提供的扩展类型，支持基本的算术运算（ + , - , * , / , % ）。

该类型不支持标准输入输出流（ cin / cout ），需通过自定义函数将数值转换为字符串或字符逐位处理以完成输入输出。