[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 G: qwb去面试 [找规律]【思维】
[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 G: qwb去面试 [找规律]【思维】
2017-06-03 02:27:50 Tabris_ 阅读数:593
博客爬取于2020-06-14 22:40:16
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849668
题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=6
——————————————————————————————————————————
Problem G: qwb去面试
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1627 Solved: 260
[Submit][Status][Web Board]
Description
某一天,qwb去WCfun面试,面试官问了他一个问题:把一个正整数n拆分成若干个正整数的和,请求出这些数乘积的最大值。
qwb比较猥琐,借故上厕所偷偷上网求助,聪明的你能帮助他吗?
Input
第一行为一个正整数T.(T<=100000)
接下来T行,每行一个正整数n(n<=1e9),意义如题目所述。
Output
每一行输出一个整数,表示乘积的最大值,由于答案可能很大,请将答案对109+7取模后输出。
Sample Input
2
2
5
Sample Output
2
6
HINT
2=2
5=2+3
——————————————————————————————————————————
一定是素数的成绩会最大
最开始以为要素因子展开,然后发现,不对,
222<3*3
然后就发现了是尽可能的拆成3
余1就将一个变成4
余2就在乘2
应该有严谨的证明之类的吧,但是我不会。
附本题代码
——————————————————————————————————————————
1 | # include <bits/stdc++.h> |