首页 > 代码库 > P4746 C’s problem(c)
P4746 C’s problem(c)
时间: 1000ms / 空间: 655360KiB / Java类名: Main
背景
冬令营入学测试
描述
题目描述
小C是一名数学家,由于它自制力比较差,经常通宵研究数学问题。
这次它因为这个数学问题已经两天两夜没有睡觉了,再不研究出来就要出人命了!快帮帮它吧!
这个问题是这样的,有一个数n,将其拆分成若干自然数之和,要求乘积最大!
如果你以为问题仅仅这么简单,那你就太naive了。
由于小C挑战自己的自我修养,它规定分成的自然数两两之间一定不能相等!
它请你输出这个乘积最大是多少,但这个答案太大了,小C并没有兴趣看那么长的数字,它只想知道这个数对1000000007取模后的值是多少。
输入格式
一行一个数表示n
输出格式
一个数表示答案
备注
输入样例
6
输出样例
8
数据范围
对于30%的数据n<=10。
对于50%的数据n<=10000。
对于100%的数据1<=n<=1000000000。
1 #define LL long long 2 3 #include<iostream> 4 using namespace std; 5 6 const LL mod=1000000007; 7 LL n,num=2,ans=1; 8 LL a[100010],s=0; 9 10 int main()11 {12 cin>>n;13 if(n<=5)14 {15 cout<<n<<endl;16 return 0;17 }18 while(n>=num)19 {20 n-=num;21 a[++s]=num;22 num++;23 }24 while(n>0)25 {26 for(int i=s;i>=1;i--)27 if(n>0)28 {29 a[i]++;30 n--;31 }32 }33 for(int i=1;i<=s;i++)34 ans=(ans*a[i])%mod;35 cout<<ans<<endl;36 return 0;37 }
P4746 C’s problem(c)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。