3382. Multiplying Digits

单点时限: 4.0 sec

内存限制: 256 MB

For every positive integer we may obtain a non-negative integer by multiplying its digits. This defines a function $f$, e.g. $f(38) = 24$.

This function gets more interesting if we allow for other bases. In base $3$, the number $80$ is written as $2222$, so: $f_3(80) = 16$.

We want you to solve the reverse problem: given a base $B$ and a number $N$, what is the smallest positive integer $X$ such that $f_B(X) = N$?

输入格式

The input consists of a single line containing two integers $B$ and $N$, satisfying $2 < B \leq 10~000$ and $0 < N < 2^{63}$.

输出格式

Output the smallest positive integer solution $X$ of the equation $f_B(X) = N$. If no such $X$ exists, output the word impossible. The input is carefully chosen such that $X < 2^{63}$ holds (if $X$ exists).

样例

Input
10 24
Output
38
Input
9 216
Output
546
Input
10 11
Output
impossible
Input
10000 5810859769934419200
Output
5989840988999909996

1 人解决,1 人已尝试。

1 份提交通过,共有 1 份提交。

8.9 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,11 月前.

最后提交: 2 年,11 月前.

来源: 2016 Benelux Algorithm Programming Contest (BAPC 16)

题目标签