Detachment

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1283 Accepted Submission(s): 364

Problem Description

In a highly developed alien society, the habitats are almost infinite dimensional space.
In the history of this planet,there is an old puzzle.
You have a line segment with x units’ length representing one dimension.The line segment can be split into a number of small line segments:

Input

The first line is an integer T,meaning the number of test cases.
Then T lines follow. Each line contains one integer x.
1≤T≤10^6, 1≤x≤10^9

Output

Maximum s you can get modulo 10^9+7. Note that we wants to be greatest product before modulo 10^9+7.

Sample Input

1
4

Sample Output

4

解题思路:
 【题意】


给定一个自然数x，让你给出一种拆分方式x=a1+a2+...(ai≠aj)，使得每个小部分的乘积s=a1*a2*...最大

【类型】

贪心构造

【分析】

此题关键在于得出如何能使乘积s最大

按照以往经验，必然是取一段连续自然数能够使得乘积最大，而这段连续自然数可从2开始(为啥不从1开始?从1开始还不如将这个1给这段连续自然数的最后一个数)，于是我们可以得到形如2+3+4+...+k(k=2,3,...)的式子，而x是10^9内的任意整数，我们不可能恰好能够凑成连续自然数之和，可能会多出△x

而这个△x的值，我可以保证它的范围为0≤△x≤k，相信大于等于0还是好理解的，为什么会小于等于k呢?因为当它大于k时，原式不是可以增加一项?即2+3+4+...+k+(k+1)

那么多出来的△x怎么处理呢?显然是从后往前均摊给连续自然数中的(k-1)个数，为啥从后往前?因为若我们从前往后，总是会使连续自然数重复，不好处理

于是，在我们分配完△x之后，我们大致会得到下述两种式子:

①2*3*...*(i-1)*(i+1)*...*k*(k+1)

②3*4*...*i*(i+1)*...*k*(k+2)

显然，我们要计算此结果，可以借助阶乘，而阶乘中缺失的项，我们除掉就可以了，那么便会涉及除法取模，显然需要用到乘法逆元

做法讲解完毕，以下是为什么连续段乘积最大的大概证明:



简而言之，假如有一个数让你拆成两个要求积最大，肯定是拆成两个一样的，如果拆成n个，肯定就是拆成这个数/n，如果没说几个，肯定都拆成2，比如10,5*5=25,2^5=32.这个题要求不能一样的，所以肯定就是2,3,4这样排列了，从2开始让它变小，这样数量会最多，每次加一就是让他越来越接近。所以用前缀和记录，如果有剩余的话，肯定是从后往前逐个+1，而且剩余的那个数最多=2,3,4...最大的那个数，举个例子会发现有两种情况：1.比如2*3*4*5余下5，相等。最优就是3*4*5*7，就是每个数都加一遍，然后会剩下一个1，加给最后一个，总的来说就是
 
除以2，乘上t+2,（t是最后一个数的值）；2.不相等，2,3,4,5，余2，最优就是2,3,5,6，就是用3的阶乘*6的阶乘除以4的阶乘，因为数量太多，不能一个一个乘，就用前缀积相除，数字太大，就要用逆元了。。然后用二分优化下。。
这题找到贪心策略后，要知道数据量大的话要用前缀积+逆元求，用前缀和优化找余数。。二分也是优化这个的
分析转自：http://blog.csdn.net/qq_34374664/article/details/53466435

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
const int N=1005;
const int mod=1e9+7;
ll ans[100005],mul[100005],t,n;
//45000项
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b){x=1;y=0;}
    else
    {
        exgcd(b,a%b,y,x);
        y-=x*(a/b);
    }
}
ll fic(ll a,ll b)//扩展欧几里得求逆元
{
    ll d,x,y;
    exgcd(a,b,x,y);
    return (x+b)%b;
}
ll fei(ll a,ll b)//费马定理
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%MOD;
        b>>=1;
        a=(a*a)%MOD;
    }
    return ans;
}
void init()
{
    memset(ans,0,sizeof(ans));
    memset(mul,0,sizeof(mul));
    ans[1]=0;
    mul[1]=1;
    for(int i=2;i<100000;i++)
    {
        ans[i]=ans[i-1]+i;
        mul[i]=(mul[i-1]*i)%MOD;
    }
}
int main()
{
    init();
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        if(n<=4){printf("%lld
",n);continue;}
        ll l=2,r=99995,mid;
        while(l<r)
        {
            mid=(l+r+1)>>1;
            if(ans[mid]<=n) l=mid;
            else r=mid-1;
        }
        ll pos=n-ans[l];
        if(pos==0) printf("%I64d
",mul[l]);
        /*else if(pos==l) printf("%I64d
",mul[l]*fic(2,MOD)%MOD*(l+2)%MOD);
        else printf("%I64d
",mul[l-pos]*mul[l+1]%MOD*fic(mul[l-pos+1],MOD)%MOD);*/
        else if(pos==l) printf("%I64d
",mul[l]*fei(2,MOD-2)%MOD*(l+2)%MOD);
        else printf("%I64d
",mul[l-pos]*mul[l+1]%MOD*fei(mul[l-pos+1],MOD-2)%MOD);
    }
    return 0;
}