“B君啊,你当年的伙伴都不在北京了,为什么你还在北京呢?”
“大概是因为出了一些事故吧,否则这道题就不叫避难所了。”
“唔,那你之后会去哪呢?”
“去一个没有冬天的地方。”
对于一个正整数 n,我们定义他在 b 进制下,各个位上的数的乘积为 p=F(n,b)。
比如 F(3338,10)=216。
考虑这样一个问题,已知 p 和 b,求最小的 n 满足 p=F(n,b)。
这是一个非常有趣的问题,对于一些 b 来说,我们可以贪心来做,比如如果 b=10,p=216。
我们可以从 b−1 到 2 试除,直到 p 为 1 为止,答案是 389,可以验证 389 是满足 p=F(n,b) 最小的 n。
但是对于一些进制 b,是不能用贪心做的,比如 b=9,p=216。使用贪心得到的解是 3338,而最优解是 666。(均为 9 进制下的。)
本题便是在给定进制 b 的情况下,举出一个这样的反例,或指出这样的反例不存在。
由于计算资源所限,反例中所有数字的乘积不能超过 1018。如果最小的反例中所有数字的乘积超过了 1018,那么也应该输出 −1。