AC日记——C’s problem(c) TYVJ P4746 (清北学堂2017冬令营入学测试第三题)

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=>1

  2=>2

  3=>3

  4=>4

  从5开始,就不等于它本身了

  5=>2*3=5

  6=>2*4=8

  7=>3*4=12

  8=>3*5=15

  9=>2*3*4=24

  10=>2*3*5=30

  11=>2*4*5=40

  12=>3*4*5=60

  13=>3*4*6=72

  14=>2*3*4*5=120

  看出规律了吧

  嗯嗯。

  如果你继续往下读,相信你也没看出来—.—

  我们可以发现n分解出的数都是从2或者3开始往后一次加

  第i个数和两边的数最大相差不过是2

  然后n每次增加1

  它里面的数总有一个要加1

  或者是最大的一个数被分解成2和max_a-1

  9=>2*3*4

  9里面的数是挨个的

  现在给9+1=10,则

  10=>2*3*5

  9里面的4被加了1

  现在给10+1成为11,则

  11=>2*4*5

  10里面的3+1成为4

  现在给11+1=12,则

  12=>3*4*5

  11里的最小的数2给加了1成为3

  再给12+1=13,则

  13=>3*4*6

  12里的5+1成为6

  在给13+1,则

  14=2*3*4*5

  应该是13里的4+1成为5,但是,这个却是6+1=7,7再被分解成2+5

  所以,这个规律就显而易见了

  把当前已经分解的k个数从第一个到第k个遍历

  如果ai[i+1]-a[i]>0

  则ai[i]++

  然后,如果这个ai[1]!=2

  那么就是ai[k]++

  直到ai[k]可以分解为2,和一个大于ai[k-1]的数

  不断循环的这个过程,知道求出n的最优分解的数

  现在你可以去写代码了

  但是,如果你真的按这个思路写了个大模拟

  超时稳稳的

  所以,你要自己优化一下

来,上代码:

#include <cstdio>
#include <iostream> #define mod 1000000007 using namespace std; int num,now= ; long long int ai[],n,ans= ; int main()
{
cin>> n;
if(n<)
{
cout<< n << endl;
return ;
}
while(now<=n)
{
ai[++num]= now;
n-= now;
now++;
}
while(n>=num+)
{
n-= num+;
ai[++num]= ++now;
}
for(int i=num;i>=&&n>;i--)
{
ai[i]+= ;
n--;
}
if(n>)
{
ai[num]+=n;
}
for(int i=;i<=num;i++)
{
ans=(ans*ai[i])%mod;
}
cout<< ans << endl;
return ;
}
上一篇:HUNNU-10307-最优分解问题


下一篇:javascript – 未在ie11中定义的FileReader和JSON对象