首页 > 代码库 > 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)