seuOJ469 - 整数划分

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：迎新赛, 2023

题目描述

给定一个正整数 $n$。要求将 $n$ 成若干个正整数之和，并且使这些正整数的乘积最大。

例如，$n=13$，则当 $n$ 表示为 $4+3+3+3$（或$2+2+3+3+3$）时，乘积$=108$为最大。

输入格式

一个正整数$n(1\le n \le 31000)$。

保证在给定的范围内，最大乘积的位数不超过 $5000$ 位。

输出格式

第 $1$ 行输出一个整数，为最大乘积的位数。 第 $2$ 行输出最大乘积的高位 $100$ 位，如果不足 $100$ 位，则按实际位数输出最大乘积。

样例

输入样例1

13

输出样例1

3
108

输入样例2

1012

输出样例2

161
8218670649826245944980599366462354031861280648818440943263708399986549619544506955820876773013288043

提示
样例 $1$ 的解释已经在题目描述中给出。