P4157 [SCOI2006] Integer Partition

Read a positive integer $n$ from the file ($10 \le n \le 31000$). You need to write $n$ as a sum of several positive integers, and make the product of these integers as large as possible. For example, when $n=13$, if $n$ is written as $4+3+3+3$ (or $2+2+3+3+3$), the product $=108$ is maximal.

One line with a positive integer $n$.

Line 1: output an integer, the number of digits of the maximum product. Line 2: output the first 100 digits of the maximum product. If it has fewer than 100 digits, output the maximum product with its actual number of digits.

Constraints For all testdata, $10 \le n \le 31000$, and it is guaranteed that the number of digits of the maximum product does not exceed 5000 digits. Translated by ChatGPT 5