P4226 [Tsinghua Training 2017] Shelter

“B, all your old friends have left Beijing. Why are you still in Beijing?” “Probably because of some accidents. Otherwise this problem wouldn’t be called ‘Shelter’.” “Hmm, where will you go next?” “To a place without winter.”

For a positive integer $n$, we define the product of its digits in base $b$ as $p = F(n, b)$. For example, $F(3338, 10) = 216$. Consider the following task: given $p$ and $b$, find the smallest $n$ such that $p = F(n, b)$. This problem is quite interesting. For some bases $b$, we can solve it greedily. For example, if $b = 10, p = 216$, we can try dividing $p$ by integers from $b - 1$ down to $2$ until $p$ becomes $1$. The answer is $389$, and you can verify that $389$ is the smallest $n$ satisfying $p = F(n, b)$. However, for some bases $b$, this greedy approach does not work. For instance, when $b = 9, p = 216$, the greedy solution is $3338$, while the optimal answer is $666$ (both in base $9$). In this problem, for a given base $b$, either produce such a counterexample or state that no such counterexample exists. Due to limited computing resources, in any counterexample the product of all digits must not exceed $10^{18}$. If in the smallest counterexample the product of all digits exceeds $10^{18}$, you should output $-1$.

Read from standard input. The first line contains an integer $t$, the number of test cases. Each of the next $t$ lines contains an integer $b$, the base.

Output to standard output. If no counterexample exists, output a single integer $-1$. If a counterexample exists, first output an integer $k$, the number of digits of $n$ in the counterexample. Then, on the same line, output $k$ decimal integers, which represent any optimal solution (the digits of the smallest $n$ for that counterexample) in base $b$.

- For the 1st subtask (30 points), $1 \leq b \leq 32$. - For the 2nd subtask (40 points), $1 \leq b \leq 100$. - For the 3rd subtask (30 points), $1 \leq t \leq 200, 1 \leq b \leq 100000$. Translated by ChatGPT 5