开始 2021-05-13 00:00:00

2011 年江苏省信息与未来夏令营

结束 2022-05-13 00:00:00
Contest is over.
当前 2025-04-12 02:04:14

G. 最大乘积

描述

将给出的一个正整数X(3≤X≤5000)分成任意个不相同的正整数,使得分成的这任意个正整数的和正好等于X、并且每个数均不相同,同时还要满足这分成的任意个正整数的乘积最大。

例如:X=9 时

9=1+8 1×8=8

=2+7 2×7=14

=... ...

=... ...

=1+2+6 1×2×6=12

=2+3+4 2×3×4=24

=... ...

列举出所有可能的分解之后,得到的最大乘积为 24,其数字之和为6

输入

一个整数N

输出

一个整数(即合理分解中的最大乘积的数字之和)。

样例

输入

20

输出

9

提示

2开始,依次加1,多余的,从尾部向头部+1,如16,16=2+3+4+5+(余数为2),所以最后为16=2+3+5+6


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交