OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2006】整数划分

【题目描述】

从文件中读入一个正整数n,要求将n写成若干个正整数之和,并且使这些正整数的乘积最大。 例如,n=13,则当n表示为4+3+3+3(或2+2+3+3+3)时,乘积=108为最大。

【输入】

只有一个正整数:n。

【输出】

第1行输出一个整数,为最大乘积的位数。 第2行输出最大乘积的前100位,如果不足100位,则按实际位数输出最大乘积。 (提示:在给定的范围内,最大乘积的位数不超过5000位)。

【输入样例】

13

【输出样例】

3

108

【数据范围】

10≤n≤31000

【题解】

喏,严格证明我还真不会0.0

大概是知道划分出的数全为e(自然对数的底数)时乘积是极限,而题目要求整数,3比2更接近e,所以尽可能的多划分出3,在小于等于4的时候划分出两个2(可以理解为两个2相比一个1与一个3更接近e^2)。

听说这是小学奥数……

【代码】

终于1A了一题了……~~o(>_<)o ~~

http://paste.ubuntu.com/8473582/

评论

© OI技术宅 | Powered by LOFTER